2018 USAJMO Problems/Problem 1

Problem

For each positive integer $n$ , find the number of $n$ -digit positive integers that satisfy both of the following conditions: [list] [*] no two consecutive digits are equal, and [*] the last digit is a prime. [/list]

Solution 1

The answer is $\boxed{\frac{2}{5}\left(9^n+(-1)^{n+1}\right)}$ .

Suppose $a_n$ denotes the number of $n$ -digit numbers that satisfy the condition. We claim $a_n=4\cdot 9^{n-1}-a_{n-1}$ , with $a_1=4$ . [i]Proof.[/i] It is trivial to show that $a_1=4$ . Now, we can do casework on whether or not the tens digit of the $n$ -digit integer is prime. If the tens digit is prime, we can choose the digits before the units digit in $a_{n-1}$ ways and choose the units digit in $3$ ways, since it must be prime and not equal to the tens digit. Therefore, there are $3a_{n-1}$ ways in this case.

If the tens digit is not prime, we can use complementary counting. First we consider the number of $(n-1)$ -digit integers that do not have consecutive digits. There are $9$ ways to choose the first digit and $9$ ways to choose the remaining digits. Thus, there are $9^{n-1}$ integers that satisfy this. Therefore, the number of those $(n-1)$ -digit integers whose units digit is not prime is $9^{n-1}-a_{n-1}$ . It is easy to see that there are $4$ ways to choose the units digit, so there are $4\left(9^{n-1}-a_{n-1}\right)$ 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},$ and our claim has been proven.

Then, we can use induction to show that $a_n=\frac{2}{5}\left(9^n+(-1)^{n+1}\right)$ . It is easy to see that our base case is true, as $a_1=4$ . Then, $\begin{aligned} a_{n + 1} & = 4 \cdot 9^{n} - a_{n} \\ = 4 \cdot 9^{n} - \frac{2}{5} (9^{n} + (- 1)^{n + 1}) \\ = 4 \cdot 9^{n} - \frac{2}{5} \cdot 9^{n} - \frac{2}{5} (- 1)^{n + 1} \\ = (4 - \frac{2}{5}) \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} (9^{n + 1} + (- 1)^{n + 2}), \end{aligned}$ as desired. $\square$

Solution by TheUltimate123.

These problems are copyrighted © by the Mathematical Association of America, as part of the American Mathematics Competitions.

2018 USAJMO (Problems • Resources)
First Problem	Followed by Problem 2
1 • 2 • 3 • 4 • 5 • 6
All USAJMO Problems and Solutions

Page

Toolbox

Search

2018 USAJMO Problems/Problem 1

Problem

Solution 1

See also