読者です 読者をやめる 読者になる 読者になる

PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 301 / Nim

Nimは2人のプレイヤーがいくつかの山に分かれた石を交互にとっていくゲームである。次のようなNimについて考える。

  • ゲーム開始時点で3つの山がある
  • 各ターンでプレイヤーは任意の1つの山から1つ以上の任意の数の石をとる
  • すべての石がなくなり,石を取ることができなくなった最初のプレイヤーが負けとなる。

(n1,n2,n3)がそれぞれの山に残っている石の数を表すとすると

  • 後手必勝の場合 0
  • 先手必勝の場合 0以外

を返す関数 X(n1,n2,n3) が定義できる。たとえば X(1,2,3) = 0 である。なぜなら先手がどのように石をとっても後手は二つの山に同じ数の石が残るようにとることができ,その後は先手と同じように他方の山から石をとっていけば勝てるからである。具体的に書くと以下のようになる。

先手 (1,2,1)→ 後手 (1,0,1)→ 先手 (0,0,1)→ 後手 (0,0,0)

正の整数 n ≦ 2^30 のうち X(n,2n,3n) = 0 となるものはいくつあるか。

Problem 301 - Project Euler


ニムについては『ゲームにひそむ数理』(森北出版)で読みました。後手必勝の条件は n, 2n, 3n を2進法に直して桁ごとに XOR を取った結果が0になることです。
Mathematica の場合,BitXor[n, 2n, 3n] = 0 をみたす n を抽出するだけで解けます。1分におさめることを意識しなければですが。


1分におさめるにはもっと数学的につめる必要があります。手がかりになりそうなことを書いておきます。

■ 条件をみたす数の具体形

2^6 以下で条件をみたす数を2進法であらわすと,次のようになります。0は連続できますが,1は連続しません。

1, 10, 100, 101, 1000, 1001, 1010, 10000, 10001, 10010,
10100, 10101, 100000, 100001, 100010, 100100, 100101,
101000, 101001, 101010, 1000000
■フィボナッチ数との関係

私のコード中の f(n) の個数は n+2 番目のフィボナッチ数です。

これが証明できれば,この問題の解答は次の1行でおわります。
Fibonacci[32]


ゲームにひそむ数理―ゲームでみがこう!!数学的センス

ゲームにひそむ数理―ゲームでみがこう!!数学的センス