Difference between revisions of "2007 AIME II Problems/Problem 6"
(noinclude, explain more) |
m (Fixed typo in second solution) |
||
(12 intermediate revisions by 10 users not shown) | |||
Line 1: | Line 1: | ||
− | + | == Problem == | |
− | + | 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? | |
− | == 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. (Also note that 0 cannot appear as 0 cannot be the first digit of an integer.) A clear pattern emerges. |
For example, for <math>3</math> in the second column, we note that <math>3</math> is less than <math>4,6,8</math>, but greater than <math>1</math>, so there are four possible places to align <math>3</math> as the second digit. | For example, for <math>3</math> in the second column, we note that <math>3</math> is less than <math>4,6,8</math>, but greater than <math>1</math>, so there are four possible places to align <math>3</math> as the second digit. | ||
Line 9: | Line 9: | ||
{| align=center style="border:1px solid black;" | {| align=center style="border:1px solid black;" | ||
|- | |- | ||
− | | | + | | Digit || 1st || 2nd || 3rd || 4th |
|- | |- | ||
| 0 || 0 || 0 || 0 || 64 | | 0 || 0 || 0 || 0 || 64 | ||
Line 32: | Line 32: | ||
|} | |} | ||
− | 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 <math> | + | 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 <math>4^{k-1} \cdot 10 = 4^3\cdot10 = 640</math>. |
+ | |||
+ | ==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 no digit is greater 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>. | ||
== See also == | == See also == | ||
Line 39: | Line 42: | ||
[[Category:Intermediate Number Theory Problems]] | [[Category:Intermediate Number Theory Problems]] | ||
</noinclude> | </noinclude> | ||
+ | {{MAA Notice}} |
Latest revision as of 13:05, 29 September 2024
Contents
[hide]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. (Also note that 0 cannot appear as 0 cannot be the first digit of an integer.) 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 |
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 .
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 no digit is greater 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 .
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.