Difference between revisions of "2018 USAJMO Problems/Problem 1"
(Created page with "== Problem == For each positive integer <math>n</math>, find the number of <math>n</math>-digit positive integers that satisfy both of the following conditions: [list] [*] no...") |
|||
| Line 2: | Line 2: | ||
For each positive integer <math>n</math>, find the number of <math>n</math>-digit positive integers that satisfy both of the following conditions: | For each positive integer <math>n</math>, find the number of <math>n</math>-digit positive integers that satisfy both of the following conditions: | ||
| − | + | ||
| − | + | -no two consecutive digits are equal, and | |
| − | + | ||
| − | + | -the last digit is a prime. | |
==Solution 1== | ==Solution 1== | ||
| Line 16: | Line 16: | ||
and our claim has been proven. | and our claim has been proven. | ||
| − | Then, we can use induction to show that <math>a_n=\frac{2}{5}\left(9^n+(-1)^{n+1}\right)</math>. It is easy to see that our base case is true, as <math>a_1=4</math>. Then, | + | Then, we can use induction to show that <math>a_n=\frac{2}{5}\left(9^n+(-1)^{n+1}\right)</math>. It is easy to see that our base case is true, as <math>a_1=4</math>. Then, <cmath>a_{n+1}=4\cdot 9^n-a_n=4\cdot 9^n-\frac{2}{5}\left(9^n+(-1)^{n+1}\right)=4\cdot 9^n-\frac{2}{5}\cdot 9^n-\frac{2}{5}(-1)^{n+1},</cmath> |
| − | + | which is equal to <cmath>a_{n+1}=\left(4-\frac{2}{5}\right)\cdot 9^n-\frac{2}{5}\cdot\frac{(-1)^{n+2}}{(-1)}=\frac{18}{5}\cdot 9^n+\frac{2}{5}\cdot(-1)^{n+2}=\frac{2}{5}\left(9^{n+1}+(-1)^{n+2}\right),</cmath> | |
| − | a_{n+1} | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
as desired. <math>\square</math> | as desired. <math>\square</math> | ||
Revision as of 19:24, 18 April 2018
Problem
For each positive integer 
, find the number of -digit positive integers that satisfy both of the following conditions:
-no two consecutive digits are equal, and
-the last digit is a prime.
Solution 1
The answer is 
.
Suppose 
denotes the number of -digit numbers that satisfy the condition. We claim 
, with 
.
[i]Proof.[/i] It is trivial to show that . Now, we can do casework on whether or not the tens digit of the -digit integer is prime. If the tens digit is prime, we can choose the digits before the units digit in 
ways and choose the units digit in 
ways, since it must be prime and not equal to the tens digit. Therefore, there are 
ways in this case.
If the tens digit is not prime, we can use complementary counting. First we consider the number of 
-digit integers that do not have consecutive digits. There are 
ways to choose the first digit and ways to choose the remaining digits. Thus, there are 
integers that satisfy this. Therefore, the number of those -digit integers whose units digit is not prime is 
. It is easy to see that there are 
ways to choose the units digit, so there are 
numbers in this case. It follows that ![\[a_n=3a_{n-1}+4\left(9^{n-1}-a_{n-1}\right)=4\cdot 9^{n-1}-a_{n-1},\]](http://latex.artofproblemsolving.com/9/7/a/97a28a2148253c718d8d174b079bd7a8d55002a7.png)
and our claim has been proven.
Then, we can use induction to show that 
. It is easy to see that our base case is true, as . Then, ![\[a_{n+1}=4\cdot 9^n-a_n=4\cdot 9^n-\frac{2}{5}\left(9^n+(-1)^{n+1}\right)=4\cdot 9^n-\frac{2}{5}\cdot 9^n-\frac{2}{5}(-1)^{n+1},\]](http://latex.artofproblemsolving.com/c/2/4/c2498fca2eec44b80ab2a4639a9ff70e8b4ae54d.png)
which is equal to ![\[a_{n+1}=\left(4-\frac{2}{5}\right)\cdot 9^n-\frac{2}{5}\cdot\frac{(-1)^{n+2}}{(-1)}=\frac{18}{5}\cdot 9^n+\frac{2}{5}\cdot(-1)^{n+2}=\frac{2}{5}\left(9^{n+1}+(-1)^{n+2}\right),\]](http://latex.artofproblemsolving.com/6/1/8/618f4ef3ff861966ab9da1f5fe3ed0442fa8f810.png)
as desired. 
Solution by TheUltimate123.
These problems are copyrighted © by the Mathematical Association of America, as part of the American Mathematics Competitions. 
See also
| 2018 USAJMO (Problems • Resources) | ||
| First Problem | Followed by Problem 2 | |
| 1 • 2 • 3 • 4 • 5 • 6 | ||
| All USAJMO Problems and Solutions | ||
