Difference between revisions of "2007 AIME II Problems/Problem 6"
(→Solution 2) |
(→Solution) |
||
Line 2: | Line 2: | ||
</noinclude>An [[integer]] is called ''parity-monotonic'' if its [[decimal representation]] <math>a_{1}a_{2}a_{3}\cdots a_{k}</math> satisfies <math>a_{i}<a_{i+1}</math> if <math>a_{i}</math> is [[odd]], and <math>a_{i}>a_{i+1}</math> if <math>a_{i}</math> is [[even]]. How many four-digit parity-monotonic integers are there?<noinclude> | </noinclude>An [[integer]] is called ''parity-monotonic'' if its [[decimal representation]] <math>a_{1}a_{2}a_{3}\cdots a_{k}</math> satisfies <math>a_{i}<a_{i+1}</math> if <math>a_{i}</math> is [[odd]], and <math>a_{i}>a_{i+1}</math> if <math>a_{i}</math> is [[even]]. How many four-digit parity-monotonic integers are there?<noinclude> | ||
− | == Solution == | + | == Solution 1== |
Let's set up a table of values. Notice that 0 and 9 both cannot appear as any of <math>a_1,\ a_2,\ a_3</math> because of the given conditions. A clear pattern emerges. | Let's set up a table of values. Notice that 0 and 9 both cannot appear as any of <math>a_1,\ a_2,\ a_3</math> because of the given conditions. A clear pattern emerges. | ||
Line 31: | Line 31: | ||
| 9 || 0 || 0 || 0 || 64 | | 9 || 0 || 0 || 0 || 64 | ||
|} | |} | ||
+ | |||
==Solution 2: Recursion== | ==Solution 2: Recursion== | ||
This problem can be solved via recursion since we are "building a string" of numbers with some condition. We want to create a new string by adding a new digit at the front so we avoid complications(<math>0</math> can't be at the front and do digit is less than <math>9</math>). There are <math>4</math> options to add no matter what(try some examples if you want so the recursion is <math>S_n=4S_{n-1}</math> where <math>S_n</math> stands for the number of such numbers with <math>n</math> digits. Since <math>S_1=10</math> the answer is <math>\boxed{640}</math>. | This problem can be solved via recursion since we are "building a string" of numbers with some condition. We want to create a new string by adding a new digit at the front so we avoid complications(<math>0</math> can't be at the front and do digit is less than <math>9</math>). There are <math>4</math> options to add no matter what(try some examples if you want so the recursion is <math>S_n=4S_{n-1}</math> where <math>S_n</math> stands for the number of such numbers with <math>n</math> digits. Since <math>S_1=10</math> the answer is <math>\boxed{640}</math>. |
Revision as of 13:41, 4 June 2017
Problem
An integer is called parity-monotonic if its decimal representation satisfies if is odd, and if is even. How many four-digit parity-monotonic integers are there?
Solution 1
Let's set up a table of values. Notice that 0 and 9 both cannot appear as any of because of the given conditions. A clear pattern emerges.
For example, for in the second column, we note that is less than , but greater than , so there are four possible places to align as the second digit.
Digit | 1st | 2nd | 3rd | 4th |
0 | 0 | 0 | 0 | 64 |
1 | 1 | 4 | 16 | 64 |
2 | 1 | 4 | 16 | 64 |
3 | 1 | 4 | 16 | 64 |
4 | 1 | 4 | 16 | 64 |
5 | 1 | 4 | 16 | 64 |
6 | 1 | 4 | 16 | 64 |
7 | 1 | 4 | 16 | 64 |
8 | 1 | 4 | 16 | 64 |
9 | 0 | 0 | 0 | 64 |
Solution 2: Recursion
This problem can be solved via recursion since we are "building a string" of numbers with some condition. We want to create a new string by adding a new digit at the front so we avoid complications( can't be at the front and do digit is less than ). There are options to add no matter what(try some examples if you want so the recursion is where stands for the number of such numbers with digits. Since the answer is .
For any number from 1-8, there are exactly 4 numbers from 1-8 that are odd and less than the number or that are even and greater than the number (the same will happen for 0 and 9 in the last column). Thus, the answer is .
See also
2007 AIME II (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.