代表選考合宿 2018
問題 7

$p=2,3,5$ のときは明らかに先手必勝である．以下，$p\gt 5$ とし，$\text{mod} ~ p$ における $10$ の位数を $a$ とする．フェルマーの小定理より $(p-1)/a$ は整数であることに注意せよ．以下，$(p-1)/a$ の偶奇で場合分けをして先手の必勝法が構成できる．

• $(p-1)/a$ が奇数のとき
  $a$ は偶数なので，$10^{a/2}\equiv -1\pmod{p}$ であり，先手は以下の戦略を取ることで

  $$\sum_{k=0}^{p-1}10^{k}a_k=0+\sum_{j}(10^ja_j+10^{j^\prime}a_{j^\prime})\equiv \sum_{j}(10^ja_j-10^{j}a_{j})\equiv 0\pmod{p}$$

  を実現することができる．

  • 先手ははじめに $i=0$ に対して $a_0=0$ を定め，後手が $i=j$ に対して $a_j$ を定めるたびに $a$ で割った商が $j$ に等しく，余りが $j-(a/2)$ のそれに等しい整数 $j^\prime$ を選び，$a_{j^\prime}=a_j$ を定める．

• $(p-1)/a$ が偶数のとき
  $(p-1)/2$ は $a$ の倍数なので $10^{(p-1)/2}\equiv 1\pmod{p}$ であり，先手は以下の戦略を取ることで

  $$\sum_{k=0}^{p-1}10^{k}a_k=0+\sum_{j}(10^ja_j+10^{j^\prime}a_{j^\prime})\equiv \sum_{j=1}^{(p-1)/2}9\cdot 10^j=10(10^{(p-1)/2}-1)\equiv 0\pmod{p}$$

  を実現することができる．

  • 先手ははじめに $i=0$ に対して $a_0=0$ を定め，後手が $i=j$ に対して $a_j$ を定めるたびに $p$ で割った余りが $j+(p-1)/2$ のそれに等しい整数 $j^\prime$ を選び，$a_{j^\prime}=9-a_j$ を定める．