AoPS - Problem

Source:

Tags: recursion, algebra

kapsitis

22.07.2016 23:22

The integer sequence $(s_i)$ "having pattern 2016'" is defined as follows: $\circ$ The first member $s_1$ is 2. $\circ$ The second member $s_2$ is the least positive integer exceeding $s_1$ and having digit 0 in its decimal notation. $\circ$ The third member $s_3$ is the least positive integer exceeding $s_2$ and having digit 1 in its decimal notation. $\circ$ The third member $s_3$ is the least positive integer exceeding $s_2$ and having digit 6 in its decimal notation. The following members are defined in the same way. The required digits change periodically: $2 \rightarrow 0 \rightarrow 1 \rightarrow 6 \rightarrow 2 \rightarrow 0 \rightarrow \ldots$. The first members of this sequence are the following: $2; 10; 11; 16; 20; 30; 31; 36; 42; 50$. What are the 4 numbers that immediately follow $s_k = 2016$ in this sequence?

pco

23.07.2016 13:03

kapsitis wrote: The integer sequence $(s_i)$ "having pattern 2016'" is defined as follows: $\circ$ The first member $s_1$ is 2. $\circ$ The second member $s_2$ is the least positive integer exceeding $s_1$ and having digit 0 in its decimal notation. $\circ$ The third member $s_3$ is the least positive integer exceeding $s_2$ and having digit 1 in its decimal notation. $\circ$ The third member $s_3$ is the least positive integer exceeding $s_2$ and having digit 6 in its decimal notation. The following members are defined in the same way. The required digits change periodically: $2 \rightarrow 0 \rightarrow 1 \rightarrow 6 \rightarrow 2 \rightarrow 0 \rightarrow \ldots$. The first members of this sequence are the following: $2; 10; 11; 16; 20; 30; 31; 36; 42; 50$. What are the 4 numbers that immediately follow $s_k = 2016$ in this sequence? 1) If $k\equiv 1\pmod 4$ : We got $2016$ looking for a $2$ and so $s_{k-1}=2015$ (else $2015$ matches instead of $2016$) So we got $s_{k-1}=2015$ looking for a $6$. Impossible. 2) If $k\equiv 2\pmod 4$ : We got $2016$ looking for a $0$ and so $s_{k-1}=2015$ (else $2015$ matches instead of $2016$) So we got $s_{k-1}=2015$ looking for a $2$ and so $s_{k-2}=2014$ (else $2014$ matches instead of $2015$) So we got $s_{k-2}=2014$ looking for a $6$. Impossible. 3) If $k\equiv 3\pmod 4$ : We got $2016$ looking for a $1$ and so $s_{k-1}=2015$ (else $2015$ matches instead of $2016$) So we got $s_{k-1}=2015$ looking for a $0$ and so $s_{k-2}=2014$ (else $2014$ matches instead of $2015$) So we got $s_{k-2}=2014$ looking for a $2$ and so $s_{k-3}=2013$ (else $2013$ matches instead of $2014$) So we got $s_{k-3}=2013$ looking for a $6$. Impossible. 4) So $k\equiv 0\pmod 4$ and we got $2016$ looking for a $6$ And the four next values are trivially $\boxed{2017,2018,2019,2026}$

Numitor

09.07.2022 07:18

Don't all cases lead to contradiction? If we follow pco procedure in $k\equiv 0\pmod 4$ we have something like this: we got $2016$ looking for a $6$ then we got $2015$ looking for a $1$ which clearly is there. then we got $2014$ looking for a $0$ which is there. then we got $2013$ looking for a $2$ which is there. but once we reach $2012$ it clearly doesn't have a $6$ as a digit. The least positive number which has a $6$ is $2006$. Similarly if we look at the official solution they devised a proof like this.

] We have a total of 4 different sequences that repeat periodically: $$ 2 \rightarrow 0 $$$$ 0 \rightarrow 1 $$$$ 1 \rightarrow 6 $$$$ 6 \rightarrow 2 $$$$ 2 \rightarrow 0 $$$$ \vdots $$To know what are the next four numbers after $s_k = 2016$ we have to know what step in the sequence does the number $2016$ map to. To make it clearer: $$2 \xrightarrow{2 \Rightarrow 0} 10 \xrightarrow{0 \Rightarrow 1} 11\xrightarrow{1 \Rightarrow 6}16\xrightarrow{6 \Rightarrow 2} 20 \xrightarrow{2 \Rightarrow 0}30 \xrightarrow{0 \Rightarrow 1}31\xrightarrow{1 \Rightarrow 6}36\xrightarrow{6 \Rightarrow 2} 42\xrightarrow{2 \Rightarrow 0} 50 \ldots$$. We now use casework to find such value: Case 1: $6 \rightarrow 2$: Then the number before $s_k=2016$ must contain a $6$ as well, and the only number before $2016$ that has $6$ as a digit is $s_{k-1}=2006$, but the next number in the sequence must be the least positive integer that has a $2$ and we find that $s_k= 2007$ has that property. Contradiction. Case 2: $ 2 \rightarrow 0 $: Then the number before must be $s_{k-1}=2015$ since it has the property that it has a $2$ as one of their digits, but the previous move is $ 6 \rightarrow 2 $ therefore we check back and find that $s_{k-2}=2006$ is the number we look for and by Case 1 we know the next number is $2007$ again contradiction. Case 3: $ 0 \rightarrow 1 $: The number before $s_k=2016$ that has a $0$ is again $s_{k-1}=2015$, the move before $s_{k-1}=2015 $is $2 \rightarrow 0$ and we find that $s_{k-2}= 2014$ works, and the move before $s_{k-2}= 2014$ is $ 6 \rightarrow 2 $ and by Case 1 we have a contradiction. Then we are left with Case 4: $ 1 \rightarrow 6 $ works since have $2016$ looking for a $6$ and therefore the next value in the sequence is $ 6 \rightarrow 2 $ then the least positive value next to it is $2017$ and following the pattern $ 2 \rightarrow 0 $ we have $2018$ as the next number, then $ 0 \rightarrow 1$ we have $2019$ and lastly $ 1 \rightarrow 6$ we have as the last number $2026$

But according to the proof given we have that: $$ 2006 \xrightarrow{6 \Rightarrow 2}2013\xrightarrow{2 \Rightarrow 0}2014\xrightarrow{0 \Rightarrow 1} 2015\xrightarrow{1 \Rightarrow 6} 2016 \ldots$$. But according to the logic of the proof given we have again a contradiction since the smallest number after $2006$ that has 2 is $2007$ not $2013$. Is there something that I'm not understanding?