#author("2021-11-04T02:24:54+00:00","","")
*[[Problem 301:http://projecteuler.net/problem=301]] 「Nim」 [#c2f75f9e]

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

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

(&tex(n_{1});,&tex(n_{2});,&tex(n_{3});)がそれぞれの山に残っている石の数を表すとすると
(&tex(n_{1});,&tex(n_{2});,&tex(n_{3});) がそれぞれの山に残っている石の数を表すとすると
- 後手必勝の場合 0
- 先手必勝の場合 0以外
- 先手必勝の場合 0 以外

を返す関数 '''X'''(&tex(n_{1});,&tex(n_{2});,&tex(n_{3});) が定義できる.
を返す関数 '''X'''(&tex(n_{1});, &tex(n_{2});, &tex(n_{3});) が定義できる.

例えば, '''X'''(1,2,3) = 0 である. ~
例えば, '''X'''(1, 2, 3) = 0 である. ~
なぜなら先手がどのように石をとっても, 後手は二つの山に同じ数の石が残るようにとることができ, ~
その後は先手と同じように他方の山から石をとっていけば勝てるからである. ~
具体的に書くと以下ようになる
- 先手 (1,2,1)
- 後手 (1,0,1)
- 先手 (0,0,1)
- 後手 (0,0,0)
- 先手 (1, 2, 1)
- 後手 (1, 0, 1)
- 先手 (0, 0, 1)
- 後手 (0, 0, 0)

正の整数 &tex(n ≦ {2}^{30}); のうち '''X'''('''n''',2'''n''',3'''n''') = 0 となるものはいくつあるか.
正の整数 &tex{n}; ≦ &tex{{2}^{30}}; のうち '''X'''('''n''', 2'''n''', 3'''n''') = 0 となるものはいくつあるか.

IP:219.106.167.72 TIME:"2021-11-04 (木) 11:24:54" REFERER:"http://odz.sakura.ne.jp/projecteuler/index.php" USER_AGENT:"Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:93.0) Gecko/20100101 Firefox/93.0"

トップ   編集 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS