Difference between revisions of "2018 USAJMO Problems/Problem 1"
m (→Solution 1) |
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]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 22:57, 20 July 2018
Contents
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
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,
which is equal to
as desired.
Solution by TheUltimate123.
Solution 2
The answer is .
As in the first solution, let denote the number of
-digit numbers that satisfy the condition. Clearly
and
. We claim that for
we have the recurrence
.
To prove this, we split the -digit numbers satisfying the conditions into cases depending on whether or not the second digit is
. If the second digit is nonzero, our number is formed from one of the
numbers with one fewer digit satisfying the conditions, times
possible choices of adding a digit to the left. If the second digit is zero, our number is formed from one of the
numbers with two fewer digits satisfying the conditions, times
possible choices of adding
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 , where the
are constants to be determined from the initial conditions
and
, and
and
are the roots of the corresponding quadratic equation
. We solve and get
, so our roots are
and
. Now, we use our conditions
and
to derive the system of linear equations
Solving this system yields and
, 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.
See also
2018 USAJMO (Problems • Resources) | ||
First Problem | Followed by Problem 2 | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAJMO Problems and Solutions |