Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2018 USAJMO Problems/Problem 1"

(→‎Solution 1 and Solution 2)
m (→‎Solution 1)
Line 10: Line 10:
  
 
Suppose <math>a_n</math> denotes the number of <math>n</math>-digit numbers that satisfy the condition. We claim <math>a_n=4\cdot 9^{n-1}-a_{n-1}</math>, with <math>a_1=4</math>.
 
Suppose <math>a_n</math> denotes the number of <math>n</math>-digit numbers that satisfy the condition. We claim <math>a_n=4\cdot 9^{n-1}-a_{n-1}</math>, with <math>a_1=4</math>.
−
[i]Proof.[/i] It is trivial to show that <math>a_1=4</math>. Now, we can do casework on whether or not the tens digit of the <math>n</math>-digit integer is prime. If the tens digit is prime, we can choose the digits before the units digit in <math>a_{n-1}</math> ways and choose the units digit in <math>3</math> ways, since it must be prime and not equal to the tens digit. Therefore, there are <math>3a_{n-1}</math> ways in this case.
+
[i]Proof.[\i] It is trivial to show that <math>a_1=4</math>. Now, we can do casework on whether or not the tens digit of the <math>n</math>-digit integer is prime. If the tens digit is prime, we can choose the digits before the units digit in <math>a_{n-1}</math> ways and choose the units digit in <math>3</math> ways, since it must be prime and not equal to the tens digit. Therefore, there are <math>3a_{n-1}</math> ways in this case.
  
 
If the tens digit is not prime, we can use complementary counting. First we consider the number of <math>(n-1)</math>-digit integers that do not have consecutive digits. There are <math>9</math> ways to choose the first digit and <math>9</math> ways to choose the remaining digits. Thus, there are <math>9^{n-1}</math> integers that satisfy this. Therefore, the number of those <math>(n-1)</math>-digit integers whose units digit is not prime is <math>9^{n-1}-a_{n-1}</math>. It is easy to see that there are <math>4</math> ways to choose the units digit, so there are <math>4\left(9^{n-1}-a_{n-1}\right)</math> numbers in this case. It follows that <cmath>a_n=3a_{n-1}+4\left(9^{n-1}-a_{n-1}\right)=4\cdot 9^{n-1}-a_{n-1},</cmath>
 
If the tens digit is not prime, we can use complementary counting. First we consider the number of <math>(n-1)</math>-digit integers that do not have consecutive digits. There are <math>9</math> ways to choose the first digit and <math>9</math> ways to choose the remaining digits. Thus, there are <math>9^{n-1}</math> integers that satisfy this. Therefore, the number of those <math>(n-1)</math>-digit integers whose units digit is not prime is <math>9^{n-1}-a_{n-1}</math>. It is easy to see that there are <math>4</math> ways to choose the units digit, so there are <math>4\left(9^{n-1}-a_{n-1}\right)</math> numbers in this case. It follows that <cmath>a_n=3a_{n-1}+4\left(9^{n-1}-a_{n-1}\right)=4\cdot 9^{n-1}-a_{n-1},</cmath>

Revision as of 21:56, 20 July 2018

Problem

For each positive integer $n$, find the number of $n$-digit positive integers that satisfy both of the following conditions:

$\bullet$ no two consecutive digits are equal, and

$\bullet$ the last digit is a prime.

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, \[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},\] 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),\] as desired. $\square$

Solution by TheUltimate123.

Solution 2

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

As in the first solution, let $a_n$ denote the number of $n$-digit numbers that satisfy the condition. Clearly $a_1 = 4$ and $a_2 = 32$. We claim that for $n \geq 3$ we have the recurrence $a_n = 8a_{n-1} + 9a_{n-2}$.

To prove this, we split the $n$-digit numbers satisfying the conditions into cases depending on whether or not the second digit is $0$. If the second digit is nonzero, our number is formed from one of the $a_{n-1}$ numbers with one fewer digit satisfying the conditions, times $8$ possible choices of adding a digit to the left. If the second digit is zero, our number is formed from one of the $a_{n-2}$ numbers with two fewer digits satisfying the conditions, times $9$ possible choices of adding $0$ and then any nonzero digit to the left. This proves our claim.

This gives us a linear three-term recurrence. It is well-known that its solution is of the form $c_1r_1^n + c_2r_2^n$, where the $c_i$ are constants to be determined from the initial conditions $a_1$ and $a_2$, and $r_1$ and $r_2$ are the roots of the corresponding quadratic equation $x^2 = 8x + 9$. We solve and get $(x-9)(x+1) = 0$, so our roots are $r_1 = 9$ and $r_2 = -1$. Now, we use our conditions $a_1 = 4$ and $a_2 = 32$ to derive the system of linear equations

\[9c_1 - c_2 = 4\] \[81c_1 + c_2 = 32\]

Solving this system yields $c_1 = \frac{2}{5}$ and $c_2 = -\frac{2}{5}$, and we are done.

Solution by putnam-lowell.


The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

See also

2018 USAJMO (Problems • Resources)
First Problem Followed by
Problem 2
1 • 2 • 3 • 4 • 5 • 6
All USAJMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2018_USAJMO_Problems/Problem_1&oldid=96386"