One hundred sages play the following game. They are waiting in some fixed order in front of a room. The sages enter the room one after another. When a sage enters the room, the following happens - the guard in the room chooses two arbitrary distinct numbers from the set {$1,2,3$}, and announces them to the sage in the room. Then the sage chooses one of those numbers, tells it to the guard, and leaves the room, and the next enters, and so on. During the game, before a sage chooses a number, he can ask the guard what were the chosen numbers of the previous two sages. During the game, the sages cannot talk to each other. At the end, when everyone has finished, the game is considered as a failure if the sum of the 100 chosen numbers is exactly $200$; else it is successful. Prove that the sages can create a strategy, by which they can win the game.
Problem
Source: ARO 2021 9.8
Tags: combinatorics
28.04.2021 09:46
Really nice problem!, initially I thought this would be very easy, because it seemed obvious that the sages could be able to avoid just one number as the eventual sum. But as it turns out, I think that if the condition was changed to the sum of the chosen numbers cannot be $200$ or $201$, then I think the guard can actually ensure that the sages cannot guarantee a win. Also, I've probably written the solution badly because I didnt know how better to explain it All sages except for the last use the following strategy: 1. If the previous two numbers chosen were $1, 1$, then they choose the smallest number available 2. If the previous two numbers chosen were $2, 1$ or $3, 1$, then they choose the number $1$ if possible, else choose $3$ 3. In all other cases, choose the smallest number available The last sage has the following strategy: 1. If the previous number chosen was $1$, then choose the smallest number available 2. Otherwise, choose the number $1$ if possible, else choose the number $3$ Now, I'll show that this strategy works. Define the deviation after $k$ sages have passed as $2k - S_k$ where $S_k$ is the sum of the $k$ numbers chosen so far. So, choosing $2$ keeps deviation same, choosing $3$ reduces it by $1$ and choosing $1$ increases it by $1$. The sages only lose if the deviation at the end is $0$ Observe that the deviation at any point is always nonnegative. This is because the only thing that can reduce it, a $3$, is only chosen if a $1$ was chosen the previous move and so the $31$ balance each other out. Also, see that the guard cannot let $1$ be chosen twice in a row since that would cause the deviation to become at least $2$ and from that point on, the deviation does not reduce any further until $99$ sages are done choosing. The last sage can reduce the deviation by at most $1$ and so the deviation at the end is at least $1$ and so the sages win. So now, observe that if $1$ is ever chosen, then the next sage, according to the strategy will pick $3$ since the guard has to not let him pick $1$, according to the previous paragraph. So, the net deviation is $0$. So, we can see that after $98$ or $99$ sages are done, the net deviation is still $0$. First, suppose net deviation after $98$ sages is $0$ but not after $99$. So, the 99th sage picks the number $1$, making the deviation $1$. But now, according to the strategy, the last sage picks the smallest number, which is $1$ or $2$, which cannot decrease the deviation and so the deviation at the end is $\ge 1$ and the sages win Finally, the last case is when after $99$ sages, the deviation is $0$. Obviously, this means that the 99th sage did not pick $1$ since otherwise this means that the deviation after $98$ sages was $0$, which is the previous case. So, according to the strategy, the last sage picks $1$ or $3$, which makes the deviation nonzero and so the sages win.
13.03.2022 16:59
Let $s_1,s_2,\ldots,s_{100}$ be the sages ; $T(s_i)$ be the set given by the guard to $s_i$ ; $N(s_i)$ number chosen by $s_i$ ; $B(s_i)$ be $N(s_{i-2})N(s_{i-1})$. By convention, we define $N(s_{-2}),N(s_{-1}) = 2$ (so that $B(s_1),B(s_2)$ are well defined). The strategy for $s_i$ is following: If $1 \le i \le 99$, then If $T(s_i) = \{1,3\}$, take $N(s_i) = 1$. $T(s_i) = \{2,a\}$ with $a \in \{1,3\}$. If $B(s_i)$ is $21$ or $31$, take $N(s_i) = a$. Otherwise, take $N(s_i) = 2$. If $i=100$, then If $T(s_{100}) = \{1,3\}$, take $N(s_i) = 1$. $T(s_{100}) = \{2,a\}$ with $a \in \{1,3\}$. If $B(s_i)$ is $21$ or $31$, take $N(s_i) = 2$. Otherwise, take $N(s_i) = a$. We show this strategy works now. Firstly, in the sequence $\mathcal S = N(s_1),N(s_2),\ldots,N(s_{99})$, change all instances of $1,3$ by $2,2$. We can do this as the sum remains same while our strategy for $s_i$ (with $1 \le i \le 99$) was same for $B(s_i)$ to be $\{13,22\}$ and $\{31,21\}$ (so our strategy isn't disturbed). By strategy, it isn't hard to see in $\mathcal S$ cannot contain a $2,1,2$. Also, as before each $3$ we had a $1$, so in the sequence there are no more $3$'s in $\mathcal S$ now. So $\mathcal S$ now looks something like $$ 2,\ldots, 2, \underbrace{1,\ldots,1}_{\text{at least two}}, 2 , \ldots , 2, \underbrace{1 , \ldots , 1}_{\text{at least two}}, 2 , \ldots, 2, \cdots $$Suppose $k$ is the number of $1$'s among $s_1,\ldots,s_{99}$. We have several cases: $k = 0$. Then $\mathcal S$ must be $2,2,\ldots,2$. Then $s_{100} \ne 2$ by strategy, so sum isn't $200$. $k=1$. Then $\mathcal S$ must be $2,2,\ldots,2,1$. Then $s_{100} = 2$ by strategy, so sum isn't $200$. $k \ge 2$. Then even if $s_{100} = 3$, the sum still is still $< 200$. This completes the proof. $\blacksquare$
10.06.2023 05:58
An interesting and surprisingly difficult problem. Shift everything by $-2$, so the set is $\{-1,0,+1\}$ and the sages wish to avoid $0$. The first $98$ sages employ the following strategy: if the last number chosen was $1$, but the number chosen before that was not $1$, then choose the number $3$ if possible, otherwise choose the number $1$. Otherwise, choose the smallest number available, which is at most $0$. If a $+1$ is ever chosen in the first $99$ numbers, the number immediately before it must be a $-1$. On the other hand, every $-1$ not adjacent to a $+1$ must be adjacent to a $-1$, except for possibly the $99$-th number chosen. Therefore, unless the $99$-th number is a $-1$, the sum of the first $99$ numbers is either $0$ or at most $-2$, otherwise it is at most $-1$. The $100$-th sage then looks at the $99$-th number chosen. If it is a $-1$, then they choose the smallest number, and the final sum is negative. Otherwise, they choose an odd number, which is always possible, making the final sum either at most $-1$ or $1$. In either case, they win. $\blacksquare$