Determine whether or not there exists a natural number $N$ which satisfies the following three criteria: 1. $N$ is divisible by $2^{2023}$, but not by $2^{2024}$, 2. $N$ only has three different digits, and none of them are zero, 3. Exactly 99.9% of the digits of $N$ are odd.
Problem
Source: INAMO 2023 P4 (OSN 2023)
Tags: number theory, Digits, NT construction, Indonesia, Indonesia MO
29.08.2023 10:02
INAMO 2023/4 wrote: Determine whether there exists a positive integer $N$ that satisfies the following three conditions: $N$ is divisible by $2^{2023}$, but is not divisible by $2^{2024}$. The decimal representation of $N$ contains exactly $3$ distinct digits (with at least one even and odd digit) and $N$ doesn't have any $0$ in its decimal representation. Exactly $99.9\%$ digits of the decimal representation of $N$ are odd numbers. My favorite problem from the N shortlist this year although I don't think it's that bad. Glad it shows up Here's the solution I found while testsolving which abuses the size constraint. The answer is yes. We'll start with the following claim. Claim 01. Fix $k \in \mathbb{N}$. There exists a positive integer $N_k > 10^{k + 1}$ such that: $N_k$ is divisible by $2^k$, but is not divisible by $2^{k + 1}$. The decimal representation of $N_k$ contains only the digits $1, 7$ and $8$ (and everything is used at least once). Proof. We'll prove this statement by induction on $k \in \mathbb{N}$. This statement is trivial for $k = 1$, just take $N_1 = 178$. Now suppose that this statement is true for all $k = \ell$. We'll prove this statement for $k = \ell + 1$. Construct $M_{\ell + 1} = \underbrace{N_\ell \cdots N_\ell}_{3 \ \text{times}}$ by concatenating $3$ number of $N_\ell$. We see that $M_{\ell + 1} > 10^{\ell + 2}$ and by construction, $\nu_2(M_{\ell + 1}) = \nu_2(N_{\ell}) = \ell$. Now, we have that there exists a sign $\ast \in \{ +, - \}$ such that $M_{\ell + 1} \ast 10^{\ell} \equiv 2^{\ell + 1} \pmod{2^{\ell + 2}}$. To see this, we first see that $2^{\ell + 1} \mid M_{\ell + 1} \pm 10^{\ell}$ as $\nu_2(M_{\ell + 1}) = \nu_2(10^{\ell}) = \ell$. Now, as $\nu_2((M_{\ell + 1} + 10^{\ell}) - (M_{\ell + 1} - 10^{\ell})) = \nu_2(2 \cdot 10^{\ell}) = \ell + 1$, then we can't have $M_{\ell + 1} \pm 10^{\ell}$ both being $0 \pmod{2^{\ell + 2}}$, as desired. For convenience, let $X = M_{\ell + 1} \ast 10^{\ell}$. We will now use this number to construct $N_{\ell + 1}$. Write $X$ in its decimal representation: \[ X = \sum_{i = 0}^{n} a_i 10^i \ \text{where } 0 \le a_i \le 9, \ \forall 0 \le i \le n \]By inductive hypothesis, $N_{\ell}$ contains only digits $1, 7$ and $8$ and thus by our construction, $a_i \in \{ 1, 7, 8 \} \ \forall 0 \le i \le n, i \not= \ell$. Now, let us define \[ N_{\ell + 1} = \sum_{i = 0}^n b_i 10^i, \ \text{where} \] $b_i = a_i$ for all $0 \le i \le n$, excluding $i = \ell$ and $i = \ell + 1$. If $a_\ell \in \{ 1, 5, 9 \}$, then $b_{\ell} = 1$ and $b_{\ell + 1} = a_{\ell + 1}$. If $a_\ell \in \{ 2, 6 \}$, then $b_{\ell} = 8$ and $b_{\ell + 1} = \begin{cases} 8 &\text{if } a_{\ell + 1} \ \text{is odd} \\ 1 &\text{otherwise} \end{cases}$. If $a_{\ell} \in \{ 0, 4, 8 \}$, then $b_{\ell} = 8$ and $b_{\ell + 1} = a_{\ell + 1}$. If $a_{\ell} \in \{ 3, 7 \}$, then $b_{\ell} = 7$ and $b_{\ell + 1} = a_{\ell + 1}$. We can now see that all digits of $N_{\ell + 1}$ are $1, 7$ or $8$ and each digit appears at least once by the definition of $M_{\ell + 1}$ (and we're only changing $2$ digits from the concatenation). We'll now prove that $N_{\ell + 1} \equiv X \pmod{2^{\ell + 2}}$, which proves the desired result. To see this, we just see that \[ N_{\ell + 1} - X = 10^{\ell + 1}(b_{\ell + 1} - a_{\ell + 1}) + 10^{\ell}(b_{\ell} - a_{\ell}) \]Consider two cases: If $a_{\ell} \in \{ 0, 1, 3, 4, 5, 7, 8, 9 \}$, we have $4 \mid b_{\ell} - a_{\ell}$ and $b_{\ell + 1} - a_{\ell + 1}$ and hence $2^{\ell + 2} \mid N_{\ell+ 1} - X$ which is what we want. If $a_{\ell} \in \{ 2, 6 \}$, we have $b_{\ell} - a_{\ell} \equiv 2 \pmod{4}$ and $b_{\ell + 1} - a_{\ell + 1} \equiv 1 \pmod{2}$, which proves what we want. From the claim above, there exists $N_{2023} > 10^{2024}$ such that $\nu_2(N_{2023}) = 2023$, where decimal representation of $N$ contains only digits $1, 7$ and $8$. The idea is now to pad digits in front of $N_{2023}$ with $1$ or $8$ depending on the current percentage of odd digits used in the representation of $N_{2023}$. To be more precise, write $N_{2023}$ in its decimal representation: \[ N_{2023} = \sum_{i = 0}^{m - 1} c_i 10^i \ \text{where } 0 \le c_i \le 9, \ \forall 0 \le i \le m - 1 \]Suppose that out of all these $m$ digits, $k$ of them are odd. Let $M$ be the smallest positive integer such that $10^{M}> m$. Define $c_m = c_{m + 1} = \dots = c_p = 1$ and $c_{p + 1} =c_{p + 2} = \dots = c_q = 8$ where $p = 999 \cdot 10^M + m - k - 1$ and $q = 10^{M + 3} - 1$. Consider the number \[ N = \sum_{i = 0}^q c_i 10^i \]and we notice that $N \equiv N_{2023} \pmod{2^{2024}}$. Furthermore, there are $(p - m + 1) + k = 999 \cdot 10^{M}$ odd digits on its decimal representation out of the total $q + 1 = 10^{M + 3}$ number of digits, and thus $N$ satisfies the given condition of the problem. Remark. The official solution constructs a $3000$-digit number $N$ that satisfies the given condition. Motivational Remark. Although the solution above seems long, the key idea of this problem is pretty simple and easy to come up with. Most of the other details just came down along the way when you're forcing things to work: You can naturally throw away the last condition of the problem (since that's the most bizarre condition to ensure of) by padding digits in front of your number that satisfies the other two conditions as long as your produced number is large enough. Let us try to use inductive hypothesis to construct a number that satisfies the new modular arithmetic condition, while maintaining a lot of the properties about the digits of the number from the inductive hypothesis, this results in a number that matches the description, except at one possible place. Edit the number locally so that you can preserve the modulo condition, while keeping the digits being from only $3$ possible digits.
29.08.2023 12:37
Solution from the proposer (me): We first prove a "stronger" claim:
Coming back to the initial question,
Some remarks:
03.01.2025 18:10
The answer is yes. In fact, we'll do it with two digits. Claim: We can construct a sequence $a_1$, $a_2$, $\dots{}$ such that: $a_1 = 2{}$; and $a_{i + 1} = k \cdot 10^i + a_i$ for the unique choice of $k \in \{1, 2\}$ ensuring that $2^{i + 1} \mid a_{i + 1}$. Proof. We proceed via induction. Suppose that we have chosen $a_1$, $a_2$, $\dots{}$, $a_n$ successfully. Now just note that if the two choices of $k$ both work or fail then \begin{align*} 2^n \equiv 3 \cdot 10^n + 2a_n \equiv (10^n + a_n) + (2 \cdot 10^n + a_n) \equiv 2\ell \equiv 0 \pmod{2^{n + 1}}\end{align*}for some $\ell \in \{0, 2^n\}$ since clearly $2^n \mid a_{n + 1}$ regardless of the value of $k$. This is a contradiction. $\blacksquare$ Now take $M = k \cdot 10^{2023} + a_{2023}$ for the choice of $k$ that fails when $n = 2023$; this ensures that $2^{2024} \nmid M$. Clearly we can append digits to the left of $M$ without affecting its value modulo $2^{2023}$ or modulo $2^{2024}$, so we will. Suppose $M$ has $d_1$ odd digits and $d_2$ even digits; just choose a large $A$ such that $999A > d_1$ and $A > d_2$, and append the appropriate numbers of ones and twos until we get $999A$ odd digits and $A$ even digits, as desired.