For each positive integer $n$, find the number of $n$-digit positive integers that satisfy both of the following conditions: no two consecutive digits are equal, and the last digit is a prime.
Problem
Source: 2018 USAJMO #1
Tags: USAJMO, 2018 USAJMO Problem 1
19.04.2018 02:00
Answer: $a_n=\frac{2}{5}(9^n-(-1)^n)$
19.04.2018 02:00
I got $\frac{2}{5}(9^n-(-1)^n)$
19.04.2018 02:01
recursion, $F_n=8F_{n-1}+9F_{n-2}, F_1=4, F_2=32$
19.04.2018 02:02
19.04.2018 02:04
19.04.2018 02:05
lmao I posted this first but mine was deleted
19.04.2018 02:08
Ok what am I even doing.....when I was solving for f(3), I thought 32*8=252.... this is just sad
19.04.2018 02:11
Th3Numb3rThr33 wrote: For each positive integer $n$, find the number of $n$-digit positive integers that satisfy both of the following conditions: no two consecutive digits are equal, and the last digit is a prime. This looks like HMMT...
19.04.2018 02:11
Oh my god...it turns out I was literally one step from solving #2 as well, so 14 --> 0
19.04.2018 02:13
Rip, I forgot first digit is not 0...
19.04.2018 02:15
How many points is it if i got that $a_{n}=8a_{n-1}+9a_{n-2}$??????
19.04.2018 02:16
19.04.2018 02:24
bogstop320 wrote: How many points is it if i got that $a_{n}=8a_{n-1}+9a_{n-2}$?????? 1 or 2 for nontrivial progress. It's a pretty important step, but not that hard to see, so I'm not completely sure
19.04.2018 02:24
When you forget that $\frac{4}{10} = \frac{2}{5}$...
19.04.2018 02:26
nukelauncher wrote: When you forget that $\frac{4}{10} = \frac{2}{5}$... i dont think they will take off points for that
19.04.2018 02:26
why is jmo stealing from aime now
19.04.2018 02:28
yeah @above tbh this would make a AIME #9 or #10.
19.04.2018 02:30
Would I lose points for not using the (-1)^n thing, and instead said if n is odd it's plus and even is minus?
19.04.2018 02:32
bogstop320 wrote: How many points is it if i got that $a_{n}=8a_{n-1}+9a_{n-2}$?????? That's a lot actually, because the rest is a standard characteristic polynomial to solve the recurrence, which is very straightforward if you've seen it before.
12.04.2023 04:50
Let $f(n)$ be the answer $f(n)=8*f(n-1)+9*f(n-2)$ because there are 8 possible digits to add to anything in $f(n-1)$ and you can also add $10,20, 30,...,90$ to anything in $f(n-2)$ $f(n)-8f(n-1)-9f(n-2)=0$ Assume that $f(n)=c^n$ $c^n-8c^{n-1}-9c^{n-2}=0$ $c^2-8c-9=0$ $c=-1,9$ So $f(n)=a(-1)^n+b*9^n$ $f(1)=4,f(2)=32$ So solve to get $a=-\frac{2}{5},b=\frac{2}{5}$ so the answer is $-\frac{2}{5}(-1)^n+\frac{2}{5}*9^n$
12.04.2023 05:02
S.Das93 wrote: still harder than this yrs j1 this is not true
12.04.2023 05:17
ihatemath123 wrote: S.Das93 wrote: still harder than this yrs j1 this is not true yeah dont take my word for it i have a major skill issue
19.05.2023 09:26
We claim that $a_n = 8a_{n-1} + 9a_{n-2}.$ Suppose that the second digit of $a_n$ is non-zero. Then there are $8$ different choices for the first digit and $a_{n-1}$ possible numbers for rest of the digits, including the second digit. Hence, the number of possible positive integers that has a prime last digit and no two consecutive digits are equal with the second digit being non-zero is $8a_{n-1}.$ Now, suppose that the second digit of $a_n$ is zero. Then there are $9$ different choices for the first digit and $a_{n-2}$ possible numbers for rest of the digits. Hence, the number of possible positive integers that has a prime last digit and no two consecutive digits are equal with the second digit being zero is $8a_{n-2}.$ Therefore $a_n = 8a_{n-1} + 9a_{n-2}$ and thus our claim is true. This is a linear homogenous recurrence relation and hence its characteristic polynomial is $x^2-8x+9 = (x-9)(x+1) = 0.$ Clearly, $a_1 = 4$ and $a_2 = 32.$ Thus, \[9c_1 - c_2 = 4\]\[81c_1 + c_2 = 32\]Solving this system gives $c_1 = \frac{2}{5}$ and $c_2 = -\frac{2}{5}$ so the answer is $a_n = \boxed{ \frac{2}{5}\left(9^n-(-1)^{n}\right)}.$
10.08.2023 08:27
Let $a_n$ denote the number of positive integers with $n$ digits such that no two consecutive digits are equal and the last digit is prime. Let $b_n$ denote the number of positive integers with $n$ digits such that no two consecutive digits are equal and the last digit is not prime. It follows that $$a_n + b_n = 9^n$$ To get our second recursive relation, we consider a good $n-1$ digit number. If the last digit is not prime, then we have 4 choices for the last digit. If the last digit is prime, then we have 3 choices for the last digit. It follows that $$a_n = 3a_{n-1}+4b_{n-1}$$With some manipulations left to the reader we eventually recover $$a_n = 8a_{n-1}+9a_{n-2}$$with initial conditions $a_0 = 0$ and $a_1 = 4$. We then extract $$a_n = \frac{2}{5}(9^n-(-1)^n)$$
04.09.2023 22:54
We, let $a_n$, be the number of $n-$ digit positive integers, that satisfy these conditions. Now, we have $a_1=4$, and $a_2=32.$ We, will take casework on the second digit, because if the second digit is $0,$ then the first digit has $9,$ choices, but if it is nonzero, the second digit has $8$, choices. Now, if the second digit is $0,$ we have $a_{n-2}$, ways to arrange the rest of the numbers, because there are $n-2$, digits left, hence, in this case, we have $9\cdot a_{n-2}$, possibilities. Now, if the second digit is nonzero, we have $a_{n-1}$, ways to arrange the rest of the digits, note that this is different, then when the second digit is nonzero, because, we now, have more options for the second digit. So, we have the recursion, $a_n=8\cdot a_{n-1}+9\cdot a_{n-2},$ also $a_1=4$, and $a_2=32.$ Claim: This, closed form, is $\frac{2}{5}\cdot (9^n-(-1)^n).$ Proof: We, use induction. The base, case, when $n=1$, gives us $\frac{2}{5}\cdot 10=4,$ as expected. The, inductive step, first we assume, that $a_n=\frac{2}{5}9^{n}-\frac{2}{5}(-1)^{n}$, and $a_{n+1}=\frac{2}{5}9^{n+1}-\frac{2}{5}(-1)^{n+1}$, now we can bash, this, out for $a_{n+2}$, using the recursion, we found, so in this case $9\cdot(\frac{2}{5}9^{n}-\frac{2}{5}(-1)^{n})+8\cdot (\frac{2}{5}9^{n+1}-\frac{2}{5}(-1)^{n+1})=a_{n+2}=\frac{2}{5}9^{n+2}-\frac{2}{5}(-1)^{n+2}$, we can do all this algebra, and we get that this induction holds, hence, the answer is $\boxed{\frac{2}{5}(9^n-(-1)^n)}.$
10.09.2023 12:09
First we can find the answer for numbers up to $n$ digits (including those with less than $n$ digits) is $4\cdot9^{n-1}$ by induction. Next if we define the required answer for each $n$ to be $a_n$, we can get the recurrence sequence $a_n=4\cdot9^{n-1}-a_{n-1}$. Inducting on this gives that $a_n=\dfrac{2}{5}(9^n-(-1)^n)$, which is our answer. Full proof here: https://infinityintegral.substack.com/p/usajmo-2018-contest-review
25.11.2023 08:57
Let $a_n$ be the amount of $n$-digit numbers satisfying the given conditions. Notice by appending a leading $0$ to all $(n-1)$-digit numbers, we get that \[a_n+a_{n-1} = 4 \cdot 9^{n-1}.\] Shifting $n$ to $n-1$, we get \[a_{n-1}+a_{n-2} = 4 \cdot 9^{n-2},\] and then dividing the two gives \[\frac{a_n+a_{n-1}}{a_{n-1}+a_{n-2}} = 9\]\[\implies a_n = 8a_{n-1}+9_{n-2}.\] Solving the characteristic polynomial shows us that \[a_n = c_1 9^n + c_2 (-1)^n.\] Now, using $a_0=0$ and $a_1=4$, we get that \[a_n = \boxed{\frac{2}{5} (9^n-(-1)^n)}.\]
31.12.2023 18:41
31.12.2023 20:47
We will solve using recursion. Firstly, consider the sequences which are in the form $p0q\ldots$ - we can think about these by considering only the part from $q$ onward, and then there are $9$ ways to choose $p$. Next, consider the sequences do not have a zero as their second digit and are in the form $prq\ldots$ - we can think about these by considering only the part from $r$ onward, and then there are $8$ ways to choose $p$. Thus, we can create the recursion $a_n = 8a_{n-1}+9a_{n-2}$ where $a_n$ is the amount of working ways for an $8$-digit number. The characteristic polynomial for this recursion is $x^2-8x-9 = 0$, which has roots $x = -1, 9$ and thus we have $a_n = p \cdot (-1)^n + q \cdot 9^n$. We know that $a_1 = 4$ and $a_2 = 32$, so $-p+9q = 4, p+81q = 32$. Then we get $p = -\frac{2}{5}, q = \frac{2}{5}$, so the answer is $a_n = -\frac{2}{5} \cdot (-1)^n + \frac{2}{5} \cdot 9^n$ ways for an $n$-digit number.
11.04.2024 04:48
MAA POV: this is a really nice prob for AIME #1 (rip MAA)
11.08.2024 21:49
We use recursion. Let $a_n$ be the number of $n$-digit positive integers that satisfy the conditions. We can construct such an integer in two ways. First, if the second leftmost digit is not $0$, we can take an $(n-1)$-digit positive integer that satisfies the conditions and add one of $8$ possible digits to the front of that $(n-1)$-digit integer. This gives us $8a_{n-1}$ possible integers. Next, if the second leftmost digit is $0$, then we can take an $(n-2)$-digit positive integer (because the digit to the right of that $0$ must be nonzero) and add one of $9$ possible (nonzero) digits in front of the $0$, creating a valid $n$-digit integer. This gives us $9a_{n-2}$ possible integers. Thus, we obtain the recursion $a_n = 8a_{n-1} + 9a_{n-2}$. Note that $a_1=5$ and $a_2=32$, so we can solve (via characteristic polynomial) to get $a_n=\frac 25\cdot (9^n-(-1)^n)$. $\blacksquare$
14.10.2024 06:24
Let $a_n$ be the answer for a given $n$. By caseowrk on the first few digits (namely, if they are $0$ or not), it's not hard to see that $a_n=8a_{n-1}+9a_{n-2}$ with characteristic roots $9$ and $-1$. So our answer is in the form of $a_n = c_1 \cdot 9^n + c_2 \cdot (-1)^n$ plug in initial conditions blah blah $a_n = \boxed{\frac25(9^n - (-1)^n)}$
14.10.2024 16:26
unique solution
03.01.2025 03:18
We claim the answer is $\boxed{\frac{2}{5}(9^n - (-1)^n)}$. Let $F_n$ be the number of strings of length $n$ with no $2$ consecutive digits equal, the first digit is nonzero, and the last digit is a prime. Let $Q_n$ be the number of strings of length $n$ with no $2$ consecutive digits equal, the first digit equal to $0$, and the last digit a prime. It is easy to see that $F_1 = 4, Q_1 = 0$, and $F_2 = 32, Q_2 = 4$. We get the recursive equations \[F_n = 8F_{n-1} + 9Q_{n-1}\]\[Q_n = F_{n-1}\]Substituting the second equation into the first, \[F_n = 8F_{n-1} + 9F_{n-2}\]which has the characteristic polynomial \[\lambda^2 - 8 \lambda - 9 = (\lambda - 9)(\lambda +1)\]Therefore, \[F_{n} = A \cdot 9^n + B \cdot (-1)^n\]Plugging in the values for $n =1 , 2$ and solving we get $(A,B) = (\frac{2}{5}, - \frac{2}{5})$, and we are done.