Japan 2007

Let the number called by a player in the $m$th turn be $N_m$. Then sequence $(N_1,\dots ,N_l)$ is called "history up to the $l$th turn". We call $j$ which satisfies $j\ne N_1,\dots ,N_l$ "free in the $l+1$th turn". We are going to prove a proposition that if $n\equiv 0,4,5(\mathrm{mod}6)$, $P$ can absolutely win and that if $n\equiv 1,2,3(\mathrm{mod}6)$, $Q$ can absolutely win.

a. for $0\le n\le 5$ If $n=0,1,2$, the proposition is surely true. Assume that $n=3$. If $Q$ calls $1$ or $2$ in the second turn, the sum of the numbers that $P$ has said is $5$ or $4$. Hence, $Q$ can absolutely win. Assume that $n=4$. If $P$ calls $2$ in the first turn, and calls $1$ or $4$ in the third turn, the sum of the numbers that $Q$ has said is $3$ or $6$. Hence, $P$ can absolutely win. For $n=5$, we call $(1,4)$ and $(2,5)$ a pair. If $P$ calls $3$ in the first turn, and after the turn, $P$ calls the other number of the pair including the number which $Q$ called in the last turn, then $P$ can absolutely win. With that, the proposition is proved for $0\le n\le 5$.

b. We are going to prove that if a proposition holds for $n=k$, it also holds for $n=k+6$. For $n=k$, let the player who has the winning strategy be $A$, and the other $B$. Let $M=\{k+1,k+2,k+3,k+4,k+5,k+6\}$, and presume the sets of the numbers $(k+1,k+4),(k+2,k+5)$, and $(k+3,k+6)$ to be pairs. Let the $l$th turn be $A$'s turn.

(1) In the $l$th turn, when there are some free numbers except the elements of $M$, it is only necessary for $A$ to act according to the following tactics. (a) When $A$ is $P$ and $l=1$, call the number $j$ which $A$ should call according to the winning strategy for $n=k$. (b) When $B$ called $i\in M$ in $l-1$th turn, call in the $l$th turn another number $j$ of the pair including $i$. (c) When $B$ called $i\notin M$ in the $l-1$th turn, let $c^{\prime }=(N_1^{\prime },\dots ,N_{l-1}^{\prime })$, where elements of $c$ are the elements of $c$ excluding elements of $M$, and the order of the elements of $c^{\prime }$ is similar to $c$. Then $c^{\prime }$ is the history for $n=k$. Because of the tactics (1)(b), if $B$ called an element of $M$ in $m-1$th turn ($m\le l-1$), $A$ also called an element of $M$ in the $m$th turn. With that, $l\equiv l^{\prime }(\mathrm{mod}2)$. Hence, according to the winning strategy for $n=k$, let the number $j$ be the number which $A$ should call in $l^{\prime }$th turn when given a history $c^{\prime }$, and call the number $j$ in the $l$th turn.

(2) In the $l$th turn, if all the "free" numbers are included in $M$, $A$ should act according to the following tactics. (a) When $B$ called $i\in M$ in the $l-1$th turn is included in $M$, $j\in M$ which is the pair of $i$ is free in the $l$th turn (because of (1)(b)). Then call $j$ in the $l$th turn. Until the game ends, call $j^{\prime }\in M$ which is the pair of the $i^{\prime }\in M$ called by $B$ in the last turn. (b) When the number called by $B$ in the $l-1$th turn is not included in $M$, if $i\in M$ is free in $l$th turn, the pair $j$ is also free. Then call any element $j_0\in M$, and act in the $l^{\prime }$th turn according to the following tactics ($l^{\prime }\ge l+1$). Let the number which $B$ called in $l^{\prime }-1$th turn be $i^{\prime }$, and the pair $j^{\prime }$. If $j^{\prime }$ is free in $l^{\prime }$th turn, call $j^{\prime }$ in $l^{\prime }$th turn. If there is no free number in the $l^{\prime }$th turn, then the game is over. Otherwise, call any element $i^{\prime \prime }\in M$ in the $l^{\prime \prime }$th turn.

If $A$ acts according to the tactics above, two following propositions hold. When the game is over, the sum of the numbers $j$ ($1\le j\le k$) called by $A$ is the same as one of the sums that appear when $A$ wins the game in the case of $n=k$. When the game is over, each player calls only one number of the pairs.

Consequently, when the game is over, the sum of the numbers which were called by $A$ is equivalent to one of the sums that appear when $A$ wins the game in the case of $n=k$ modulo $3$. So $A$ wins. With that, the mathematical induction is completed.

Hence, it can be said that $P$ has a winning strategy if and only if $n\equiv 0,4,5(\mathrm{mod}6)$.