ランダム・アルバイト・クイズ

http://www.hyuki.com/d/200510.html#i20051016205402
一人の場合で、ちょっと長いけれども dungeon crawl の religion.cc から。

if (one_chance_in(100))
{
    // Choose a god randomly from those to whom we owe penance.
    //
    // Proof: (By induction)
    //
    // 1) n = 1, probability of choosing god is one_chance_in(1)
    // 2) Asuume true for n = k (ie. prob = 1 / n for all n)
    // 3) For n = k + 1,
    //
    //      P:new-found-god = 1 / n (see algorithm)
    //      P:other-gods = (1 - P:new-found-god) * P:god-at-n=k
    //                             1        1
    //                   = (1 - -------) * ---
    //                           k + 1      k
    //
    //                          k         1
    //                   = ----------- * ---
    //                        k + 1       k
    //
    //                       1       1
    //                   = -----  = ---
    //                     k + 1     n
    //
    // Therefore, by induction the probability is uniform.  As for
    // why we do it this way... it requires only one pass and doesn't
    // require an array.
     int which_god = GOD_NO_GOD;
    unsigned int count = 0;
     for (int i = GOD_NO_GOD; i < NUM_GODS; i++)
    {
        if (you.penance[i])
        {
            count++;
            if (one_chance_in(count))
                which_god = i;
        }
    }
     if (which_god != GOD_NO_GOD)
        divine_retribution(which_god);
}

えっと、引用の範疇かな? 上のコードは Crawl General Public Licence がかかっております。
roguelike のソースは多くが公開されていて、ソースコード読解の練習として手ごろである。dungeon crawl の C++はひどいものの angband は美しい C言語で書かれていて、その証拠に多くの variant (変種)がある、といわれているらしい。

さて、このクイズは簡単だし特に見るところもないと思うが、前もお邪魔していたとある研究室で聞いたし、こんなところにわざわざ証明してあるということは意外性があるのだろうか。
その研究室の方は、この問題を聞いたときに、「えっと、一人目に二人目を1:1で重ね合わせて、三人目を2:1で重ね合わせて、ってやっていって最後に観測して出てきた人を選べばいい。」と答えてました。量子コンピューティング系だったので。