今週は昨日も今日も人と会う機会が多くてblogの更新も滞りがちで、特に水曜日の雨でずぶぬれになってからちょっと体調崩し気味なのをいいこと見てしまったコマネチ大学数学科。


ローマ人の物語VIII
 塩野七生

コマ大数学科とローマとの関係を知りたい方は、「続き」を。

今回の顧問は中村先生。

問題:
1から200まで順に番号を振ったカードを、一枚目を最後に最後にまわし、二枚目を捨てという操作を繰り返します。最後の一枚の番号は?

コマ大生はいつものように実践。ここではカードの代わりにポテトチップスを使って、二枚目を捨てる代わりに食べるという操作を繰り返した。マス北野は正解までの道筋を正しく認識するも、実際にそれを計算するに至らずギブアッップ。そして東大女子大生チームは、正しい、しかし洗練さが一歩およばない解法を見つけるも、計算ミスをやらかして不正解。

実は正解はコマ大生だけだったのが、コマネチフィールズ賞は、最もエレガントな解法まではたどりついたマス北野の手に。

解法をここで述べるのはヤボなので、代わりにそれをjavascriptで解くものを以下に。

カードが 枚のとき、最後に残るのは1。

Source: 
function josephus(n){
  function mask(n){
    var mask = 0;
    while(n >>= 1) mask += mask + 1;
    return mask;
  }
  var c = (~n) & mask(n);
  return n - c;
}

ここで問題。なぜmask()が必要か?

今回の問題を使ったヨセフスは、ユダヤ戦記の作者にして皇帝ティトゥスのマブダチ。そして彼を生き残らせたエピソードが、↑の「ローマ人の物語VIII」に登場します。

似たような問題を塵劫記でも見たような気がしますが、確かにヨセフスの方が先達ではありますね。

Dan the Auditor Thereof