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"

m (→‎Solution 1)
m
 
(12 intermediate revisions by 7 users not shown)
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.
+
<math>\textit{Proof.}</math> 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>
 
and our claim has been proven.
 
and our claim has been proven.
  
Line 36: Line 36:
  
 
Solution by putnam-lowell.
 
Solution by putnam-lowell.
 +
 +
==Solution 3==
 +
The answer is <math>\boxed{\frac{2}{5}\left(9^n-(-1)^{n}\right)}</math>.
 +
 +
As in the first solution, let <math>a_n</math> denote the number of <math>n</math>-digit numbers that satisfy the condition. Clearly <math>a_1 = 4</math> and <math>a_2 = 32</math>.
 +
 +
From here, we proceed by complementary counting. We first count the total amount of numbers that satisfy both bullets but that may have zero as its first digit. The units digit can be one of four primes, and each digit to the left will have 9 choices (any digit but the one that was just used). Then the total for this group of numbers is just <math>4*9^{n-1}</math>.
 +
 +
Now we must subtract all numbers in the above group that have 0 as its first digit. This is just <math>a_{n-1}</math> because for each number in the first group beginning with a zero, we could take away the zero, leaving us with a number that works for the case <math>n-1</math> (this is true because the next number would not be zero, or the consecutive digit requirement would be violated). Then we have the recursive formula <math>a_n = 4*9^{n-1}-a_{n-1}</math>.
 +
 +
To simplify this, we take a look at the first few terms. We see that
 +
 +
<cmath>a_2 = 4*9^1-a_1 = 36-4 = 4(9-1) = 4(9^1-9^0)</cmath>
 +
<cmath>a_3 = 4*9^2-a_2 = 4(81) - 4(9-1) = 4(9^2-9^1+9^0)</cmath>
 +
 +
We see a pattern where <math>a_n = 4(9^{n-1}-9^{n-2}+9^{n+3}...+(-1)^{n-1}9^0)</math> and we can prove that it holds for all <math>a_n</math> because subtracting <math>a_{n-1}</math> from <math>4(9^n)</math> is the same thing as reversing all previous signs of the preceding powers of 9. This constitutes an alternating pattern, which we can calculate as a geometric series. The first term is <math>4(9^{n-1})</math> and the common ratio is <math>-\frac{1}{9}</math>, so
 +
 +
<cmath>a_n = \frac{4(9^{n-1})(1-(-\frac{1}{9})^n)}{1-(-\frac{1}{9}))} = \frac{4(9^{n-1}-(-1)^n(\frac{1}{9}))}{\frac{10}{9}} = \frac{4(9^{n}-(-1)^n)}{10} = \frac{2}{5}\left(9^n-(-1)^{n}\right) </cmath>
 +
 +
We are done.
 +
 +
Solution by aopsal
 +
 +
==Solution 4==
 +
Let <math>f(n)</math> denote the number of <math>n</math>-digit positive integers satisfying the conditions listed in the problem.
 +
Claim 1: <math>f(n) = 8f(n-1) + 9f(n-2). </math>
 +
To prove this, let <math>k</math> be the leftmost digit of the <math>n</math>-digit positive integer. When <math>k</math> ranges from <math>1</math> to <math>9, </math> the allowable second-to-leftmost digits is the set <math>\{0, 1, 2, …, 9\}, </math> with <math>k</math> excluded. Note that since <math>1, 2, …, 9</math> are all repeated <math>8</math> times and using our definition of <math>f(n)</math> (since <math>n</math>-digit positive integers must begin with a positive digit), we have proved that <math>8f(n-1)</math> part. Since <math>0</math> is repeated <math>9</math> times, and since digits that are allowed to be adjacent to the <math>0</math> (the third-to-leftmost digit of our positive integer) are integers ranging from <math>1</math> to <math>9, </math> we have proved the <math>9f(n-2)</math> part similarly. We can see that <math>\frac{f(1)}{4} = 1</math> and <math>\frac{f(2)}{4} = 8, </math> by simple computation. These will be our base cases.
 +
Now, let <math>s(n) = \frac{f(n)}{4}.</math>
 +
Claim 2: <math>s(n+1) = 9s(n) + (-1)^n</math>
 +
We can prove this using induction. Let <math>s(a) = k</math> and <math>s(a+1) = 9k - 1. </math> By plugging <math>k</math> and <math>9k - 1</math> into our formula <math>s(a+2) = 8s(a+1) + 9s(a), </math> we obtain <cmath>s(a+2) = 8(9k-1) + 9k \implies s(a+2) = 81k - 8 = 9s(a+1) + 1.</cmath>Now, by plugging <math>9k - 1</math> and <math>81k - 8</math> into the same formula, we obtain <math>s(a+3) = 8(81k - 8) + 9(9k - 1) = 729k - 73 = 9s(a+2) - 1. </math> Since with <math>a+2</math> and <math>a+3</math> we’re back where we started (this is since <math>s(a+3) = 9s(a+2) - 1</math> just like <math>s(a+1) = 9s(a) - 1</math>), and using our base cases of <math>s(1) = 1</math> and <math>s(2) = 8, </math> our induction is complete.
 +
Claim 3: <math>s(n) = \frac{9^n + (-1)^{n+1}}{10}</math>
 +
We can prove that <cmath>s(n) = \underbrace{9(9(9(…9(9-1)+1)…-1)+1)-1}_{\text{n-1 nested parentheses}} = \sum_{i=0}^{n-1} 9^{i} (-1)^{n-i-1}</cmath>by simply using our base case of <math>s(1) = 1</math> and repeatedly using the distributive property to obtain further values of <math>s(n). </math> For the case where <math>n</math> is even, we can manipulate the summation into <math>\sum_{i=0}^{\frac{n}{2} - 1} 8 \cdot 9^{2i}</math> which equals <math>\frac{8 \cdot 9^{n} - 1}{9^2 - 1} = \frac{9^n - 1}{10}, </math> by geometric series. For the case where <math>n</math> is odd, we can manipulate the summation into <math>1 + \sum_{i=0}^{\frac{n-1}{2} - 1} 8 \cdot 9^{2i + 1}</math> which equals <cmath>9 \cdot \frac{8 \cdot 9^{n-1} - 1}{80} + 1 = \frac{9^n - 9}{10} + 1 = \frac{9^n + 1}{10}.</cmath>Thus, we have proved Claim 3 for both odd and even <math>n.</math>
 +
Since <math>f(n) = 4s(n),</math> our answer is <math>4 \cdot \frac{9^n + (-1)^{n+1}}{10} = \boxed{ \frac{2}{5} (9^n + (-1)^{n+1})}. </math>
 +
 +
-fidgetboss_4000
 +
 +
 +
==Solution 5==
 +
Let <math>a_n</math> be the number of <math>n</math>-digit numbers that satisfy the condition that most-left digit different than <math>0</math>. Let <math>b_n</math> be the number of <math>n</math>-digit numbers that satisfy the condition that most-left digit is <math>0</math>. We can write that
 +
<cmath>
 +
\left\{
 +
\begin{split}
 +
a_n + b_n & = 4\cdot 9^{n-1} \\
 +
b_n & = a_{n-1}
 +
\end{split}
 +
\right.
 +
</cmath>
 +
and so we find that
 +
<cmath> a_n + a_{n-1}  = 4\cdot 9^{n-1} \tag{1}</cmath>
 +
<math>x+1</math> is the characteristic polynomial of the homogeneous recurrence relation <math>a_n + a_{n-1}  = 0 </math>. Then <math>x=-1</math> is a root. Also, by the non-homogeneous part of <math>4\cdot 9^{n-1}</math>, we understand that <math>x=9</math> is another root of the recurrence relation <math>(1)</math> with the complementary solution idea. Therefore, <math>(a_n)</math> sequence in the form <cmath> a_n =C_19^n + C_2(-1)^n .</cmath>
 +
We can calculate that <math>C_1 = \dfrac{2}{5}, C_2 = - \dfrac{2}{5}</math> with using <math>a_1=4, a_2=32</math>. Thus we get:
 +
<cmath> a_n = \dfrac{2}{5}\left(9^{n} - (-1)^{n} \right) </cmath>
 +
 +
Lokman GÖKÇE
 +
 +
 +
 +
==Video Solution==
 +
https://www.youtube.com/watch?v=1BijQXkC5dg
 +
-Osman Nal
 +
-inserted by srisainandan6
  
  

Latest revision as of 10:37, 28 February 2023

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$. $\textit{Proof.}$ 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.

Solution 3

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$.

From here, we proceed by complementary counting. We first count the total amount of numbers that satisfy both bullets but that may have zero as its first digit. The units digit can be one of four primes, and each digit to the left will have 9 choices (any digit but the one that was just used). Then the total for this group of numbers is just $4*9^{n-1}$.

Now we must subtract all numbers in the above group that have 0 as its first digit. This is just $a_{n-1}$ because for each number in the first group beginning with a zero, we could take away the zero, leaving us with a number that works for the case $n-1$ (this is true because the next number would not be zero, or the consecutive digit requirement would be violated). Then we have the recursive formula $a_n = 4*9^{n-1}-a_{n-1}$.

To simplify this, we take a look at the first few terms. We see that

\[a_2 = 4*9^1-a_1 = 36-4 = 4(9-1) = 4(9^1-9^0)\] \[a_3 = 4*9^2-a_2 = 4(81) - 4(9-1) = 4(9^2-9^1+9^0)\]

We see a pattern where $a_n = 4(9^{n-1}-9^{n-2}+9^{n+3}...+(-1)^{n-1}9^0)$ and we can prove that it holds for all $a_n$ because subtracting $a_{n-1}$ from $4(9^n)$ is the same thing as reversing all previous signs of the preceding powers of 9. This constitutes an alternating pattern, which we can calculate as a geometric series. The first term is $4(9^{n-1})$ and the common ratio is $-\frac{1}{9}$, so

\[a_n = \frac{4(9^{n-1})(1-(-\frac{1}{9})^n)}{1-(-\frac{1}{9}))} = \frac{4(9^{n-1}-(-1)^n(\frac{1}{9}))}{\frac{10}{9}} = \frac{4(9^{n}-(-1)^n)}{10} = \frac{2}{5}\left(9^n-(-1)^{n}\right)\]

We are done.

Solution by aopsal

Solution 4

Let $f(n)$ denote the number of $n$-digit positive integers satisfying the conditions listed in the problem. Claim 1: $f(n) = 8f(n-1) + 9f(n-2).$ To prove this, let $k$ be the leftmost digit of the $n$-digit positive integer. When $k$ ranges from $1$ to $9,$ the allowable second-to-leftmost digits is the set $\{0, 1, 2, …, 9\},$ with $k$ excluded. Note that since $1, 2, …, 9$ are all repeated $8$ times and using our definition of $f(n)$ (since $n$-digit positive integers must begin with a positive digit), we have proved that $8f(n-1)$ part. Since $0$ is repeated $9$ times, and since digits that are allowed to be adjacent to the $0$ (the third-to-leftmost digit of our positive integer) are integers ranging from $1$ to $9,$ we have proved the $9f(n-2)$ part similarly. We can see that $\frac{f(1)}{4} = 1$ and $\frac{f(2)}{4} = 8,$ by simple computation. These will be our base cases. Now, let $s(n) = \frac{f(n)}{4}.$ Claim 2: $s(n+1) = 9s(n) + (-1)^n$ We can prove this using induction. Let $s(a) = k$ and $s(a+1) = 9k - 1.$ By plugging $k$ and $9k - 1$ into our formula $s(a+2) = 8s(a+1) + 9s(a),$ we obtain \[s(a+2) = 8(9k-1) + 9k \implies s(a+2) = 81k - 8 = 9s(a+1) + 1.\]Now, by plugging $9k - 1$ and $81k - 8$ into the same formula, we obtain $s(a+3) = 8(81k - 8) + 9(9k - 1) = 729k - 73 = 9s(a+2) - 1.$ Since with $a+2$ and $a+3$ we’re back where we started (this is since $s(a+3) = 9s(a+2) - 1$ just like $s(a+1) = 9s(a) - 1$), and using our base cases of $s(1) = 1$ and $s(2) = 8,$ our induction is complete. Claim 3: $s(n) = \frac{9^n + (-1)^{n+1}}{10}$ We can prove that \[s(n) = \underbrace{9(9(9(…9(9-1)+1)…-1)+1)-1}_{\text{n-1 nested parentheses}} = \sum_{i=0}^{n-1} 9^{i} (-1)^{n-i-1}\]by simply using our base case of $s(1) = 1$ and repeatedly using the distributive property to obtain further values of $s(n).$ For the case where $n$ is even, we can manipulate the summation into $\sum_{i=0}^{\frac{n}{2} - 1} 8 \cdot 9^{2i}$ which equals $\frac{8 \cdot 9^{n} - 1}{9^2 - 1} = \frac{9^n - 1}{10},$ by geometric series. For the case where $n$ is odd, we can manipulate the summation into $1 + \sum_{i=0}^{\frac{n-1}{2} - 1} 8 \cdot 9^{2i + 1}$ which equals \[9 \cdot \frac{8 \cdot 9^{n-1} - 1}{80} + 1 = \frac{9^n - 9}{10} + 1 = \frac{9^n + 1}{10}.\]Thus, we have proved Claim 3 for both odd and even $n.$ Since $f(n) = 4s(n),$ our answer is $4 \cdot \frac{9^n + (-1)^{n+1}}{10} = \boxed{ \frac{2}{5} (9^n + (-1)^{n+1})}.$

-fidgetboss_4000


Solution 5

Let $a_n$ be the number of $n$-digit numbers that satisfy the condition that most-left digit different than $0$. Let $b_n$ be the number of $n$-digit numbers that satisfy the condition that most-left digit is $0$. We can write that \[\left\{ \begin{split} a_n + b_n & = 4\cdot 9^{n-1} \\ b_n & = a_{n-1} \end{split} \right.\] and so we find that \[a_n + a_{n-1} = 4\cdot 9^{n-1} \tag{1}\] $x+1$ is the characteristic polynomial of the homogeneous recurrence relation $a_n + a_{n-1} = 0$. Then $x=-1$ is a root. Also, by the non-homogeneous part of $4\cdot 9^{n-1}$, we understand that $x=9$ is another root of the recurrence relation $(1)$ with the complementary solution idea. Therefore, $(a_n)$ sequence in the form \[a_n =C_19^n + C_2(-1)^n .\] We can calculate that $C_1 = \dfrac{2}{5}, C_2 = - \dfrac{2}{5}$ with using $a_1=4, a_2=32$. Thus we get: \[a_n = \dfrac{2}{5}\left(9^{n} - (-1)^{n} \right)\]

Lokman GÖKÇE


Video Solution

https://www.youtube.com/watch?v=1BijQXkC5dg -Osman Nal -inserted by srisainandan6


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=190370"