ご注文は数オリですか?

問題一覧へ戻る

#43
整数論
★★☆☆☆

p を奇素数とする. AnaとBenが以下のようなルールによってゲームを行う.

  • 1 以上 2p2 以下の整数を交互に一つずつ選ぶ. ただし過去に二人のいずれかによって選ばれた数は選ぶことができない.
  • すべての数が選ばれたら, 二人はそれぞれ選んだ p1 個の数の総積に 1 を足すことで, 自らのスコアを計算する.
  • 一方のスコアのみが p で割り切れるときその人の勝利となり, それ以外の場合は引き分けとなる.

Anaが先に整数を選ぶ. 互いが常に最適に行動し続けるとき, ゲームの結果はどうなるか?

渡辺:このゲーム p が地雷すぎでしょ
平山:でも引き分ける可能性はあるのか
渡辺:少なくともBenは勝てない
平山:Ana目線とBen目線どっちが良いのかな
渡辺:原始根との相性は良さげ?
平山:ただの和の問題になるね
馬杉0,1,,p22 セット分あるのか
渡辺(p1)/2 が抜けてる
馬杉:先にそれ取るくらいしか際立ったことが
平山:あとはBenと同じやつ取るとか?
馬杉:それでいいじゃん
平山:そもそも原始根見なくてもWilson…
馬杉:Wilsonの定理の再開発じゃん

  • 積の問題を和の問題に変換できるのが原始根の強みであり, 今回こそ本質では無かったが見通しが良くなることも多いので, 素数 mod のときはとりあえず考えてみると美味しいことがあるかもしれない

Anaが以下のような戦略で勝てることを示す. ここで各 1ip2 に対し組 {i,i+p}ペアと呼ぶ.

  • 最初は p1 を選ぶ.
  • それ以降は, 直前にBenが p を選んだとき, まだ要素が一つも選ばれていないペアから適当な数を選ぶ.
  • ap を選んだとき, a と同じペアに含まれるもう一方の要素 (すなわち a±p) がまだ選ばれていないならばそれを選び, そうでないならばまだ要素が一つも選ばれていないペアから適当な数を選ぶ.

Benはどこかで必ず p を選ぶことになるため, そのスコアは p の倍数になり得ない. またAnaは最終的に各ペアからちょうど一つずつ選んでいることが容易に確かめられるため, 最初の p1 と合わせてWilsonの定理よりそのスコアは p の倍数になる. よって示された.