R-bloggers で紹介されていたパズルを F# で解いてみました。

問題原文

Alice et Bob viennent de découvrir un nouveau jeu, le jeu de la « petite moitié ».

Ils posent au départ sur la table une centaine de pions environ (entre 98 et 102). Chacun des joueurs, à tour de rôle, prend, à son choix, soit un pion, soit la moitié des pions restants (si le nombre de pions est impair, il s’agit de la «petite moitié », la moitié du nombre diminué de un, appelée la partie entière de la moitié). Celui qui est contraint de prendre le dernier pion a perdu (il n’est pas possible de passer).

Bob joue le premier et, malgré son talent, se fait battre par Alice.

Quel était le nombre exact de pions au départ ?

日本語訳

Alice と Bob は "petite moitié" というゲームを考えました。

箱の中におよそ 100 個 (98 から 102 の間) の豆が入っています。交互に 1 つもしくは箱の中の半分 (残りが奇数の場合は 1 を引いてから半分にする) の豆を取っていきます。最後の豆を取った方が負けです (パスはできない)。

Bob が先手で最善を尽くしましたが Alice に負けました。

最初に箱の中にあった豆の数はいくつでしょう。

半分の定義からすると最後の 1 つになったときに半分 (= 0 個) 取るという選択がありそうですが，パスはできないので，自分の順番のときに箱の中の豆が 1 つであれば負けだと考えます。

問題文を F# で表現していきます。

まずプレイヤーとして Alice と Bob がいます。

type Player = Alice | Bob

Alice と Bob は交互に豆を取ります。

let alternate = function
   | Alice -> Bob
   | Bob -> Alice

豆の取り方は 1 つ取るか半分取るかの 2 通りです。

let takeOne n = n - 1
let takeHalf n = n - n/2

プレイヤーは各々自分が勝利できるように豆を取っていきます。

let rec turn player = function
   | 1 -> alternate player  // 残りが 1 つなら相手の勝ち
   | n ->
      let other = alternate player
      let win =  // 次の手で相手がどんな選択をしても自分が勝つ
         let nextTurn = turn other
         in nextTurn (takeHalf n) = player || nextTurn (takeOne n) = player
      if win then player else other

Bob が先手で Alice が勝ちました。

let condition =
   turn Bob  // Bob が先手で
   >> (=) Alice  // 勝者が Alice

最初に豆が 98 個から 102 個ありました。それはいくつでしょう。

let answer = [98 .. 102] |> List.filter condition  // [99]

問題文を逐語訳したらいつの間にか解答が得られていたというお話でした。

ちなみに R-bloggers の記事では半分取るときに残りの個数を誤っているために答えが違いますが，原文の方は修正されています。