Wizardに尋ねる #369
x について解きます:
9 x + 12 x = 16 x
これが私の解決策です（PDF）。
この問題は、Wizard of Oddsの私のフォーラムで質問され、議論されました。
この問題は、ビデオ「A Difficult Exponential Question」からヒントを得ました。
次の 10 桁の数字を見つけます。
- 数字の最初の桁は、数字全体に含まれる 0 の数です。
- 数字の 2 番目の桁は、数字全体に含まれる 1 の数です。
- 数字の 3 番目の桁は、数字全体に含まれる 2 の数です。
- 数字の 4 桁目は、数字全体のうちの 3 の数です。
- 数字の 5 桁目は、数字全体のうちの 4 の数です。
- 数字の6桁目は、数字全体のうちの5の数です。
- 数字の 7 桁目は、数字全体のうちの 6 の数です。
- 数字の 8 桁目は、数字全体のうちの 7 の数です。
- 数字の 9 桁目は、数字全体のうちの 8 の数です。
- 数字の 10 番目の桁は、数字全体における 9 の数です。
この質問は、Wizard of Vegasの私のフォーラムで尋ねられ、議論されています。
邪悪な看守が 100 人の囚人を集め、それぞれに 1 から 100 までの固有の番号を付けます。
別の部屋には、番号の付いた箱が100個あります。看守は1から100までの番号が付けられた紙片を取り出し、箱ごとに1枚ずつ、ランダムに箱の中に入れます。
翌日、囚人は一人ずつ箱室に入ることが許可されます。各囚人は50個の箱を開けることができます。もし囚人が自分の番号の箱を見つけた場合（例えば、23番の囚人が23の数字が書かれた箱を見つけた場合）、彼は「成功」となり、50個目の箱を開ける前に見つければ早く退出できます。退出は入口とは別のドアから行います。まだ自分の番が来ていない囚人は、前の囚人の結果を知ることはできません。
100人の囚人全員が成功すれば、全員が釈放されます。しかし、1人でも失敗した場合は、全員が直ちに死刑に処されます。
囚人たちは1日を共に過ごし、戦略を練ることが許されます。最初の囚人が箱の部屋に入った後は、それ以上のコミュニケーションは禁止されます。コミュニケーションの例としては、書類を移動させたり、蓋を開けたままにしたりすることなどが挙げられますが、これらに限定されるものではありません。コミュニケーションが発覚した場合、すべての囚人は直ちに処刑されます。
彼らが解放される可能性を最大化する戦略は何でしょうか?
[spoiler=戦略のみ]
一般的な考え方は、少なくとも1人の囚人が失敗した場合、最終的に全員が死ぬという結果は変わらないため、多くの囚人が失敗してもおかしくないというものです。したがって、優れた戦略とは、多くの囚人が失敗する可能性を犠牲にして、全員の成功確率を最大化することです。
プレイヤーが任意の箱を開ける戦略を考えてみましょう。まず、箱の中に入っている紙に書かれた数字を読み、次にその箱を開けます。次に、その箱の中の紙を読み、その数字が書かれた箱を3番目に開けます。このプロセスを繰り返すと、最終的に最初の箱に戻ります。
プレイヤーがこの戦略に従い、自分の数字がその数字のループ内のどこかにある場合、開ける箱に制限がないと仮定すると、明らかに最終的には見つけられるでしょう。
プレイヤーが必ず自分の番号を見つけられるように、自分の番号から始めることもできます。そうすれば、1回から100回まで箱を開ける必要があるかもしれませんが、最終的には自分の番号に戻ってきます。
この戦略によって最終的に最初の箱に戻る箱の集合は、閉ループと呼ばれます。閉ループ内の箱の数は、ループのサイズです。
この問題の鍵となるのは、サイズが 50 を超える閉ループが存在しない場合はすべての囚人が成功するということです。
[/ネタバレ][spoiler=解決策]
100個の閉ループがある場合、囚人は失敗します。その確率はどれくらいでしょうか？最初の箱がそれ自身に繋がらない確率は99/100です。もしそれ自身に繋がらない場合、2番目の箱が元の数字に繋がらない確率は98/99です。その箱がそれ自身に繋がらない場合、次の箱がそれ自身に繋がらない確率は97/98です。この論理を拡張すると、100個の閉ループが存在する確率は(99/100)*(98/99)*(97/88)*...*(3/4)*(2/3)*(1/2) = 1/100となります。
99個の閉ループはどうでしょうか？99個の閉ループには、1個の閉ループがもう一つ存在します。その1個の閉ループは、100個の箱のいずれかである可能性があります。どの箱も、その箱自体に繋がる確率は1/100です。残りの99個の箱については、100個の閉ループの場合の上記の論理に従うと、閉ループを形成する確率は1/99です。つまり、99個の閉ループの確率は、100 × (1/100) & (1/99) = 1/99となります。
98個の閉ループはどうでしょうか？98個の閉ループには、互いに何らかの形で繋がる2つの箱があります。1個の閉ループが2つ、または2個の閉ループが1つです。この1個の閉ループは、100個の箱のいずれかです。どの箱も、それ自身に繋がる確率は1/100です。残りの99個の箱については、100個の閉ループの場合の上記の論理に従って、閉ループを形成する確率は1/99です。したがって、99個の閉ループの確率は、100 × (1/100) × (1/99) = 1/99となります。
98個の閉ループはどうでしょうか？98個の閉ループの場合、互いに何らかの形で繋がる2つの箱が存在することになります。1個の閉ループが2つ、または2個の閉ループが1つです。100個の箱から2個の箱を選ぶ方法は、combin(100,2)=4,950通りあります。2個を選んだ場合、その2個の箱に、箱番号と一致する紙が入っている確率は、どのような組み合わせであっても、(2/100)*(1/99) = 4,950分の1です。残りの98個が閉ループを形成する確率は1/98です。つまり、98個の閉ループの確率は(4950)*(1/4950)*(1/98) = 1/98です。
この論理をたどっていくと、確率が 1/51 である 51 の閉ループに至ります。
失敗の確率は、pr(100 のクローズドループ) + pr(99 のクローズドループ) + pr(98 のクローズドループ) + ... + pr(51 のクローズドループ) = 1/100 + 1/99 + 1/98 + 1/97 + ... + 1/51 =~ 0.6881721793 です。
失敗の確率が 0.688172179 の場合、成功の確率は 1 - 0.6881721793 = 約 0.3118278207 になります。
[/ネタバレ]この質問は、Wizard of Vegasの私のフォーラムで尋ねられ、議論されています。
この質問は、この Veritasium ビデオからヒントを得ました。
100人の従業員がいるオフィスで、シークレットサンタのプレゼント交換をします。全員の名前を紙に書き、全員を帽子の中に入れて、ランダムに名前を引いてプレゼントを贈ります。
問題は、平均して閉じたループがいくつあるかということです。
サイズ 4 のクローズドループの例: Gordon が Don に渡し、Don が Jon に渡し、Jon が Nathan に渡し、Nathan が Gordon に渡す。
自分の名前を描くと、サイズ 1 の閉じたループになります。
[spoiler=解決策]
シークレットサンタパーティーに来る従業員が一人だけいるとします。当然、彼は自分で選ぶので、ループは一つになります。
すると、2人目の従業員が遅れてやって来て、一緒に行きたいと申し出ます。彼女には、今いる2人の従業員のリストが渡されます。彼女が従業員1を選ぶ確率は1/2、彼女自身が選ぶ確率は1/2です。もし彼女が従業員1を選んだ場合、彼女は従業員1のループに押し込まれ、従業員1の分を買って、彼が彼女の分を買ってくれることになります。つまり、1 + 0.5 * 1 = 1.5 となります。
すると3人目の従業員が遅れてやって来て、一緒に来たいと申し出ます。彼女には3人になった従業員のリストが渡されます。彼女が従業員1か2を選ぶ確率は2/3、彼女自身が選ぶ確率は1/3です。もし彼女が従業員1か2を選んだ場合、彼女は彼らのループに押し込まれ、自分が選んだ従業員のために買い物をし、本来その従業員のために買い物をするはずだった人が3人目の従業員のために買い物をすることになります。つまり、1.5 + (1/3) = 11/6となります。
すると4人目の従業員が遅れてやって来て、一緒に行きたいと申し出ます。彼女には4人になった従業員のリストが渡されます。彼女が従業員1から3を選ぶ確率は3/4で、彼女自身が選ぶ確率も1/4です。もし彼女が従業員1から3を選んだ場合、彼女は彼らのループに押し込まれ、自分が選んだ従業員の分を買い、本来その従業員の分を買うはずだった人が4の分を買うことになります。つまり、11/6 + (1/4) = 25/12となります。
これを続けると、最終的な答えは 1/1 + 1/2 + 1/3 + ... + 1/100 =~ 5.187377518 になります。
[/ネタバレ]この質問は、Wizard of Vegasの私のフォーラムで尋ねられ、議論されています。