Difference between revisions of "2004 AIME I Problems/Problem 6"
m (→Solution 1) |
|||
| (7 intermediate revisions by 4 users not shown) | |||
| Line 2: | Line 2: | ||
An integer is called snakelike if its decimal representation <math> a_1a_2a_3\cdots a_k </math> satisfies <math> a_i<a_{i+1} </math> if <math> i </math> is [[odd integer | odd]] and <math> a_i>a_{i+1} </math> if <math> i </math> is [[even integer | even]]. How many snakelike integers between 1000 and 9999 have four distinct digits? | An integer is called snakelike if its decimal representation <math> a_1a_2a_3\cdots a_k </math> satisfies <math> a_i<a_{i+1} </math> if <math> i </math> is [[odd integer | odd]] and <math> a_i>a_{i+1} </math> if <math> i </math> is [[even integer | even]]. How many snakelike integers between 1000 and 9999 have four distinct digits? | ||
| − | == Solution == | + | == Solution 1 == |
| + | |||
We divide the problem into two cases: one in which zero is one of the digits and one in which it is not. In the latter case, suppose we pick digits | We divide the problem into two cases: one in which zero is one of the digits and one in which it is not. In the latter case, suppose we pick digits | ||
<math>x_1,x_2,x_3,x_4</math> such that <math>x_1<x_2<x_3<x_4</math>. There are five arrangements of these digits that satisfy the condition of being snakelike: <math>x_1x_3x_2x_4</math>, <math>x_1x_4x_2x_3</math>, <math>x_2x_3x_1x_4</math>, <math>x_2x_4x_1x_3</math>, <math>x_3x_4x_1x_2</math>. Thus there are <math>5\cdot {9\choose 4}=630</math> snakelike numbers which do not contain the digit zero. | <math>x_1,x_2,x_3,x_4</math> such that <math>x_1<x_2<x_3<x_4</math>. There are five arrangements of these digits that satisfy the condition of being snakelike: <math>x_1x_3x_2x_4</math>, <math>x_1x_4x_2x_3</math>, <math>x_2x_3x_1x_4</math>, <math>x_2x_4x_1x_3</math>, <math>x_3x_4x_1x_2</math>. Thus there are <math>5\cdot {9\choose 4}=630</math> snakelike numbers which do not contain the digit zero. | ||
| − | In the second case we choose zero and three other digits such that <math>0<x_2<x_3<x_4</math>. There are three arrangements of these digits that satisfy the condition of being snakelike: <math>x_2x_30x_4</math>, <math>x_2x_40x_3</math>, <math>x_3x_40x_2</math>. Because we know that zero is a digit, there are <math>3\cdot{9\choose 3}=252</math> snakelike numbers which contain the digit zero. Thus there are <math>630+252=882</math> snakelike numbers. | + | In the second case we choose zero and three other digits such that <math>0<x_2<x_3<x_4</math>. There are three arrangements of these digits that satisfy the condition of being snakelike: <math>x_2x_30x_4</math>, <math>x_2x_40x_3</math>, <math>x_3x_40x_2</math>. Because we know that zero is a digit, there are <math>3\cdot{9\choose 3}=252</math> snakelike numbers which contain the digit zero. Thus there are <math>630+252=\boxed{882}</math> snakelike numbers. |
| + | |||
| + | == Solution 2 == | ||
| + | Let's create the snakelike number from digits <math>a < b < c < d</math>, and, if we already picked the digits there are 5 ways to do so, as said in the first solution. And, let's just pick the digits from 0-9. This get's a total count of <math>5\cdot{10 \choose 4}</math> But, this over-counts since it counts numbers like 0213. We can correct for this over-counting. Lock the first digit as 0 and permute 3 other chosen digits <math>a < b < c</math>. There are 2 ways to permute to make the number snakelike, b-a-c, or c-a-b. And, we pick a,b,c from 1 to 9, since 0 has already been chosen as one of the digits. So, the amount we have overcounted by is <math>2\cdot{9 \choose 3}</math>. Thus our answer is <math>5\cdot{10 \choose 4} - 2\cdot{9 \choose 3} = \boxed{882}</math> | ||
| + | |||
| + | == Solution 3 == | ||
| + | We will first decide the order of the 4 digits, greatest to least. To do this, we will pretend that we have selected the digits 1,2,3,4, and we need to arrange them to create a snakelike number. By testing all permutations, there are only 5 ways to make a snakelike number: (1,3,2,4),(1,4,2,3),(2,3,1,4),(2,4,1,3),(3,4,1,2). | ||
| + | |||
| + | Now we select 4 digits to replace the 1,2,3,4. | ||
| + | |||
| + | In first 2 of cases: (1,3,2,4),(1,4,2,3), the leading digit is a 1, which means it is the smallest of our 4 digits. If we select a 0, the leading digit will be a zero, which is bad because all numbers between 1000 and 9999 have nonzero leading digits. So, we need to select our 4 digits only from the pool of 1-9. There are 9 choose 4 ways and there are 2 cases: | ||
| + | |||
| + | <math>2 \cdot \dbinom{9}{4} = 252</math> | ||
| + | |||
| + | Thus, there are 252 ways for those 2 cases. | ||
| + | |||
| + | For the next 3 cases, selecting a 0 is okay, so we can select from the pool of 0-9. There are 10 choose 4 ways to select our 4 digits and there are 3 cases: | ||
| + | |||
| + | <math>3 \cdot \dbinom{10}{4} = 630</math> | ||
| + | |||
| + | For those 3 cases there are 630 ways. | ||
| + | |||
| + | Thus, our answer is 630+252 = <math>\boxed{882}</math>. | ||
| + | |||
| + | -Alexlikemath | ||
== See also == | == See also == | ||
{{AIME box|year=2004|n=I|num-b=5|num-a=7}} | {{AIME box|year=2004|n=I|num-b=5|num-a=7}} | ||
{{MAA Notice}} | {{MAA Notice}} | ||
Latest revision as of 17:12, 4 March 2022
Problem
An integer is called snakelike if its decimal representation 
satisfies 
if 
is odd and 
if is even. How many snakelike integers between 1000 and 9999 have four distinct digits?
Solution 1
We divide the problem into two cases: one in which zero is one of the digits and one in which it is not. In the latter case, suppose we pick digits
such that 
. There are five arrangements of these digits that satisfy the condition of being snakelike: 
, 
, 
, 
, 
. Thus there are 
snakelike numbers which do not contain the digit zero.
In the second case we choose zero and three other digits such that 
. There are three arrangements of these digits that satisfy the condition of being snakelike: 
, 
, 
. Because we know that zero is a digit, there are 
snakelike numbers which contain the digit zero. Thus there are 
snakelike numbers.
Solution 2
Let's create the snakelike number from digits 
, and, if we already picked the digits there are 5 ways to do so, as said in the first solution. And, let's just pick the digits from 0-9. This get's a total count of 
But, this over-counts since it counts numbers like 0213. We can correct for this over-counting. Lock the first digit as 0 and permute 3 other chosen digits 
. There are 2 ways to permute to make the number snakelike, b-a-c, or c-a-b. And, we pick a,b,c from 1 to 9, since 0 has already been chosen as one of the digits. So, the amount we have overcounted by is 
. Thus our answer is 
Solution 3
We will first decide the order of the 4 digits, greatest to least. To do this, we will pretend that we have selected the digits 1,2,3,4, and we need to arrange them to create a snakelike number. By testing all permutations, there are only 5 ways to make a snakelike number: (1,3,2,4),(1,4,2,3),(2,3,1,4),(2,4,1,3),(3,4,1,2).
Now we select 4 digits to replace the 1,2,3,4.
In first 2 of cases: (1,3,2,4),(1,4,2,3), the leading digit is a 1, which means it is the smallest of our 4 digits. If we select a 0, the leading digit will be a zero, which is bad because all numbers between 1000 and 9999 have nonzero leading digits. So, we need to select our 4 digits only from the pool of 1-9. There are 9 choose 4 ways and there are 2 cases:
Thus, there are 252 ways for those 2 cases.
For the next 3 cases, selecting a 0 is okay, so we can select from the pool of 0-9. There are 10 choose 4 ways to select our 4 digits and there are 3 cases:
For those 3 cases there are 630 ways.
Thus, our answer is 630+252 = 
.
-Alexlikemath
See also
| 2004 AIME I (Problems • Answer Key • Resources) | ||
| Preceded by Problem 5 |
Followed by Problem 7 | |
| 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
| All AIME Problems and Solutions | ||
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. 
