, 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 \neq 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 \pmod 6$, $P$ can absolutely win and that if $n \equiv 1, 2, 3 \pmod 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' = (N'_1, \dots, N'_{l-1})$, where elements of $c$ are the elements of $c$ excluding elements of $M$, and the order of the elements of $c'$ is similar to $c$. Then $c'$ 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' \pmod 2$. Hence, according to the winning strategy for $n=k$, let the number $j$ be the number which $A$ should call in $l'$th turn when given a history $c'$, 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' \in M$ which is the pair of the $i' \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'$th turn according to the following tactics ($l' \ge l+1$).
Let the number which $B$ called in $l'-1$th turn be $i'$, and the pair $j'$. If $j'$ is free in $l'$th turn, call $j'$ in $l'$th turn. If there is no free number in the $l'$th turn, then the game is over. Otherwise, call any element $i'' \in M$ in the $l''$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 \pmod 6$.