Let $S=\{13, 133, \cdots\}$ be the set of the positive integers of the form $133 \cdots 3$. Consider a horizontal row of $2022$ cells. Ana and Borja play a game: they alternatively write a digit on the leftmost empty cell, starting with Ana. When the row is filled, the digits are read from left to right to obtain a $2022$-digit number $N$. Borja wins if $N$ is divisible by a number in $S$, otherwise Ana wins. Find which player has a winning strategy and describe it.
Problem
Source: Iberoamerican 2022, Day 1, P2
Tags: number theory
29.09.2022 20:38
Surprisingly (or not), Ana has a winning strategy. Suppose on her turn Ana is going to fill the place with $10^{2n}$, then she will choose the digit in that place such that the number no longer has any hope of being divisible by either $M = 10^{2n+1} + \frac{10^{2n+1} - 1}{3}$ or $N = 10^{2n} + \frac{10^{2n} - 1}{3}$. Clearly if she can do this, then she manages to win, so it suffices to show this is possible. Say she fills $k \cdot 10^{2n}$, since all digits to the left of this are fixed, there is at most one value of $k$ which is possibly divisible by $M$ and at most $8$ values of $k$ for which it is possibly divisible by $N$ (since $8N > 10^{2n+1}$, so at most $8$ multiples of it can be in this range), so since Ana has $10$ digits, she can pick at least one of them and so wins.
29.09.2022 20:49
L567 wrote: Surprisingly (or not), Ana has a winning strategy. Suppose on her turn Ana is going to fill the place with $10^{2n}$, then she will choose the digit in that place such that the number no longer has any hope of being divisible by either $M = 10^{2n+1} + \frac{10^{2n+1} - 1}{3}$ or $N = 10^{2n} + \frac{10^{2n} - 1}{3}$. Clearly if she can do this, then she manages to win, so it suffices to show this is possible. Say she fills $k \cdot 10^{2n}$, since all digits to the left of this are fixed, there is at most one value of $k$ which is possibly divisible by $M$ and at most $8$ values of $k$ for which it is possibly divisible by $N$ (since $8N > 10^{2n+1}$, so at most $8$ multiples of it can be in this range), so since Ana has $10$ digits, she can pick at least one of them and so wins. I guess your idea is right, however Ana never places a digit in an empty cell of the form $10^{2n}$ for a $2022$- digit number (she first starts with $10^{2021}$, then $10^{2019}$ etc... So if your argument remains the same for $2n \rightarrow 2n+1$ I guess the proof suffices
29.04.2023 06:30
Solution from Twitch Solves ISL: Ana wins. All that's needed is: Claim: On Ana's $k$th move for $k=1,2,\dots,1011$, Ana can pick the digit to ensure the final number (no matter what happens after) is neither a multiple of \[ X = \underbrace{133\dots33}_{2024-2k} \]nor \[ Y = \underbrace{1333\dots33}_{2025-2k}. \] Proof. $X$ eliminates at most $8$ choices of digits while $Y$ eliminates at most $1$. $\blacksquare$
07.09.2023 04:32
Ana has a winning strategy. Let $a_n$ be the number formed by adding $n$ copies of $3$ to the right of $1$. I claim that on Ana's $i$-th move (where $1 \leq i \leq 1011$), she can guarantee that the final number is not divisible by $a_{2023-2k}$ or $a_{2024-2k}$. Indeed, on this step the possible values that $N$ could become lie in an interval of size $10^{2024-2k}$, which can contain at most $8$ multiples of $a_{2023-2k}$ and $1$ of $a_{2024-2k}$, hence one digit can be selected which cannot result in a multiple of $a_{2023-2k}$ or $a_{2024-2k}$. This finishes the problem. $\blacksquare$ Remark (motivation): It's not hard to see that Ana can guarantee $N$ isn't divisible by $13$ or $133$ with only the last digit. This is already pretty good, but results in $1010$ wasted moves and also doesn't guarantee that we can avoid divisibility by $1333$, $13333$, etc. (even though in some sense these are "unlikely" to occur). But then one realizes that we can use these remaining moves to get rid of other possible divisors and solves the problem
24.09.2023 22:00
We claim that Ana can always win. Note that only $2021$ numbers in $S$ matter. Label the elements $s_1, s_2, \dots, s_{2020} = 133, s_{2021} = 13$ such that $s_i$ has $2023 - i$ digits. Ana first chooses the first digit as $4$ such that $s_1$ can't divide $N$. Claim: For $k \ge 1$, Ana can choose the $2k + 1$ digit such that $N$ can't be divisible by either $s_{2k}$ or $s_{2k+1}$. Proof. By choosing the digit, Ana decides which of the $10$ gaps of size $10^{2022-(2k+1)}$ $N$ falls in. The numbers divisible by $s_{2k}$ cover at most $1$ gap, and the numbers divisible by $s_{2k+1}$ cover at most $\left\lceil \frac{100}{13} \right\rceil = 8$. Thus, at most $9$ gaps contain such a number, so Ana can choose the digit corresponding to the $10$th gap. $\blacksquare$ Repeating this for each of their turns guarentees a win.