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

XOR

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

フィボナッチ数

n XOR 2n XOR 3n = (n XOR 2n) XOR 3n = 0 となる条件は

n XOR 2n = 3n = n+2n

これは2進法で n+2n を計算したとき,繰り上がりがおきないということです。n の2進法表示は連続する1を含みません。

実際に 2^6 以下で条件をみたす数を2進法であらわしてみると,次のようになっています。

1, 10, 100, 101, 1000, 1001, 1010, 10000, 10001, 10010,
10100, 10101, 100000, 100001, 100010, 100100, 100101,
101000, 101001, 101010, 1000000

こういう数が何個あるか数えましょう。10→100, 10→101 のように桁数を増やしていきます。
n 桁で末尾が 0, 1 のものの個数を a(n), b(n) とおきます。0は連続して構いませんが,1は連続しないので
 a_{n+1}=a_n+b_n,\, b_{n+1}=a_n

a(n) と b(n) の和を c(n) とおくと

 c_{n+1}=a_{n+1}+b_{n+1}=(a_n+b_n)+a_n
 =c_n+(a_{n-1}+b_{n-1})
 =c_n+c_{n-1}

c(1)=c(2)=1 も言えるので,c(n) はフィボナッチ数です。

 c(n)=fib(n)

この問題では n ≦ 2^30 なので,2進法で1~30桁の数と n=2^30 を考えます。条件をみたす n の個数はこうなります。

fib(1)+fib(2)+\cdots+fib(30)+1
 =\left\{fib(32)-1\right\}+1=fib(32)


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

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