Jenga Game

Nimによる解法

最終盤面に着目すると、必ず $S_i$ は $\{1,3\},\{2\}$ のいずれかになっていることが分かります。
一つの集合に着目したときに、$\{1,3\}$ になる場合は $1$ 回の操作が、$\{2\}$ になる場合は $2$ 回の操作が必ず行われます。

これは、次の様に $N$ 個全ての山が $2$ のNimとして考えることができます。

• 集合 $S_i$ から $1,3$ のいずれかを取り除くとき、山 $i$ から石を $1$ つ取り除く。
• 集合 $S_i$ から $2$ を取り除くとき、山 $i$ から石を $2$ つ取り除く。

よって、$\bigoplus_{i=1}^N2$ が $0$ であるかどうかを考えればよく、これは $N$ が奇数の時に $2$ 、偶数の時に $0$ になります。
ここから、奇数の時にAlice、偶数の時にBobが勝つことが分かります。

真似っこ戦法による解法

$N$ が偶数の時を考えます。
Bobは以下の戦略によって必ず勝つことができます。

$S_j=\{1,2,3\}$ を満たす $j$ の個数を $a$ 、 $1\in S_j$ または $3\in S_j$ のうち一方のみを満たす $j$ の個数を $b$ とします。

ここで、 $a,b$ をどちらも偶数と仮定します。

最初は $a=N,b=0$ なので仮定は真です。

Aliceが前のターンで集合 $S_i$ から $x$ を取り除いたとします。

• $x=1,3$ の場合
  • $S_i=\{1,2,3\}$ の場合
    $2\le a$ より、$S_j=\{1,2,3\}$ なる $j(\ne i)$ が存在するので、$S_j$ から $1,3$ のいずれかを取り除きます。
    $a$ が $2$ だけ減り、仮定より $a-2$ も偶数です。
  • $S_i\ne\{1,2,3\}$ の場合
    $2\le b$ より、同じように $1\in S_j$ または $3\in S_j$ のうち一方のみを満たす $j(\ne i)$ が存在するので、$S_j$ から $1,3$ のいずれか存在する方を取り除きます。
    $b$ が $2$ だけ減り、仮定より $b-2$ も偶数です。
• $x=2$ の場合
  $2\le a$ より、$S_j=\{1,2,3\}$ なる $j$ が存在するので、$S_j$ から $2$ を取り除きます。
  $a$ が $2$ だけ減り、仮定より $a-2$ も偶数です。

$N$ が奇数の時は、最初にAliceがいずれかの集合から $2$ を取り除くことで $N$ が偶数の場合に帰着でき、Aliceが必勝となります。

実装例（C++）

1
2
3
4
5
6
7
8
9
10
11
12
13#include <bits/stdc++.h>
using namespace std;
int main()
{
  int T;
  cin >> T;
  while (T--)
  {
    int N;
    cin >> N;
    cout << (N % 2 ? "Alice" : "Bob") << endl;
  }
}