Given a positive integer whose base-$10$ representation is $\overline{d_k\ldots d_0}$ for some integer $k \geq 0$, where $d_k \neq 0$, a move consists of selecting some integers $0 \leq i \leq j \leq k$, such that the digits $d_j,\ldots,d_i$ are not all $0$, erasing them from $n$, and replacing them with a divisor of $\overline{d_j\ldots d_i}$ (this divisor need not have the same number of digits as $\overline{d_j\ldots d_i}$). Prove that for all sufficiently large even integers $n$, we may apply some sequence of moves to $n$ to transform it into $2024$. Allen Wang
Problem
Source: ELMO Shortlist 2024/N6
Tags: Elmo, number theory
23.06.2024 02:14
Replace $X0000$ with $16$, then replace any remaining $X000$, $X00$, $X0$ with $2$. Then, $n$ has all nonzero digits, is even, and is sufficiently large. By Pigeonhole, there exists a substring of digits $4-200$ that is a multiple of $101$. Replace that with $101$. Replace digits $1$, $2$, $3$ with $1$, so the number starts with $111101$, and replace $11110$ with $202$. Finally, replace the remaining digits other than the last one with $1$, the last digit with $2$, and $12$ with $4$ to get $2024$.
24.06.2024 01:31
It should also be true that given a sufficiently large even integer $n$, we can apply some sequence of moves to $n$ to transform it into any integer less than $10^{1434}$.
03.07.2024 04:09
Note that we can convert any digit into $1$ and any even digit into $2$. Thus, we begin by converting $\overline{d_2d_1d_0} \to 112$. Now, note that (as long as those digits are not affected) the number will always be divisible $8$. Thus, we only need our number to be divisible by $253 = 11 \cdot 23$. Now, let $N = \varphi(258)$ and $k$ be sufficiently large. consider the digits $d_{N}, d_{2N}, \ldots, d_{kN}$. By PHP, one can expect that at least $258$ of these digits are equal, call this digit $a$. Given that $d_{Nk_1}, \ldots, d_{Nk_{253}}$ are $a$, and $N$ is the original number, we see that we convert $d_{Nk_1}, \ldots, d_{Nk_m} $ all to $1$ we get a number $M$ satisfying \[ M \equiv N - a \cdot 10^{Nk_1} - \cdots - a \cdot 10^{Nk_m} + 1 \cdot 10^{Nk_1} + \cdots + 1 \cdot 10^{Nk_m} \]\[ \equiv N+(1-a)(10^{Nk_1} + \cdots + 10^{Nk_m}) \equiv N + (1-a)m \pmod{253}\]Note that $\gcd(a-1,253) = 1$ so there must exist some $m$ where $m(1-a) \equiv -N \pmod{253}$ so we can convert some of the digits to get a number divisible by $2024$. Thus, we can convert the whole number to $2024$ as desired.
04.07.2024 22:11
Call a positive integer $n$ "good" if it can be transformed into $2024$ like this . Claim: Any positive integer with enough digits which are $ \geq 1$ are "good". which are even. Proof: Choose all digits other than last which are $\geq 1$ and convert them to $1$ this makes the number only consist of $1$'s and $0$'s. Now convert any subseqeucnes like $10000...0$ to a signle $1$ as the no of $1$'s is still same , this makes all digits except last only consist of $1$'s as i excluded the last digit from this operation again. Case 1: the last digit is zero. Then the number obtained is like $1111...(d times)1110$ convert the last $10$ to $2$ convert this to case 2. Case 2: The last digit is non zero its easy to see last digit is even. First reduce the last number to $2$ , then we have numbers like $111....(d digits)...112$ we know there exists $k$ such that $2027|111..(k digits 1$ now reduce the $11$'s at the end to a single one untill we have $111..(k 1's)112$ reduce it to $20272$ and finally the $72$ to $4$ and u have $2024$ Now to finally to finish off the problem if the number does not have enough terms $ \geq 1$ , first reduce the terms $\geq 1$ to $1$ as there is atleast one $1$ in a large number of digits and the no of $1$'s is bounded the gaps between atleast one pair of these consequtive ones grows arbitarily large hence u can have subsequences like $10^d$ for large $d$ we can knock it off to $2^d$ and use https://math.stackexchange.com/questions/13131/starting-digits-of-2n to finish it off. by again transforming it a number with enough $1$'s
04.07.2024 22:14
blackbluecar wrote: Note that we can convert any digit into $1$ and any even digit into $2$. Thus, we begin by converting $\overline{d_2d_1d_0} \to 112$. Now, note that (as long as those digits are not affected) the number will always be divisible $8$. Thus, we only need our number to be divisible by $253 = 11 \cdot 23$. Now, let $N = \varphi(258)$ and $k$ be sufficiently large. consider the digits $d_{N}, d_{2N}, \ldots, d_{kN}$. By PHP, one can expect that at least $258$ of these digits are equal, call this digit $a$. Given that $d_{Nk_1}, \ldots, d_{Nk_{253}}$ are $a$, and $N$ is the original number, we see that we convert $d_{Nk_1}, \ldots, d_{Nk_m} $ all to $1$ we get a number $M$ satisfying \[ M \equiv N - a \cdot 10^{Nk_1} - \cdots - a \cdot 10^{Nk_m} + 1 \cdot 10^{Nk_1} + \cdots + 1 \cdot 10^{Nk_m} \]\[ \equiv N+(1-a)(10^{Nk_1} + \cdots + 10^{Nk_m}) \equiv N + (1-a)m \pmod{253}\]Note that $\gcd(a-1,253) = 1$ so there must exist some $m$ where $m(1-a) \equiv -N \pmod{253}$ so we can convert some of the digits to get a number divisible by $2024$. Thus, we can convert the whole number to $2024$ as desired. I dont think u can convert $d_1d_2d_3$ to $112$ infact not all digits can be converted to $1$ the digits which are equal $0$ exist
04.07.2024 23:30
idkk wrote: blackbluecar wrote: Note that we can convert any digit into $1$ and any even digit into $2$. Thus, we begin by converting $\overline{d_2d_1d_0} \to 112$. Now, note that (as long as those digits are not affected) the number will always be divisible $8$. Thus, we only need our number to be divisible by $253 = 11 \cdot 23$. Now, let $N = \varphi(258)$ and $k$ be sufficiently large. consider the digits $d_{N}, d_{2N}, \ldots, d_{kN}$. By PHP, one can expect that at least $258$ of these digits are equal, call this digit $a$. Given that $d_{Nk_1}, \ldots, d_{Nk_{253}}$ are $a$, and $N$ is the original number, we see that we convert $d_{Nk_1}, \ldots, d_{Nk_m} $ all to $1$ we get a number $M$ satisfying \[ M \equiv N - a \cdot 10^{Nk_1} - \cdots - a \cdot 10^{Nk_m} + 1 \cdot 10^{Nk_1} + \cdots + 1 \cdot 10^{Nk_m} \]\[ \equiv N+(1-a)(10^{Nk_1} + \cdots + 10^{Nk_m}) \equiv N + (1-a)m \pmod{253}\]Note that $\gcd(a-1,253) = 1$ so there must exist some $m$ where $m(1-a) \equiv -N \pmod{253}$ so we can convert some of the digits to get a number divisible by $2024$. Thus, we can convert the whole number to $2024$ as desired. I dont think u can convert $d_1d_2d_3$ to $112$ infact not all digits can be converted to $1$ the digits which are equal $0$ exist You can with minor adjustments.