今更ですが、Googleの入社試験
最近数学ガールの影響で、論理クイズにはまっています。
5人の海賊で金貨を山分けする問題とか、5人の奴隷を使って毒入りの樽を探しあてる問題とか、面白い問題があって楽しんで解いています。
で、昔挑戦して解けなかったGoogleの入社試験の問題があったなー、と思い出してたので、また挑戦してみることにしました。
↓の問題です。
ある村では100組の夫婦がいて、夫は全員浮気をしたことがあります。
この村の妻は自分以外の夫が浮気をしたら、それをすぐに知ることができます。
またこの村には掟があって、妻は自分の夫の浮気を知ったらその日の内に夫を殺さなければいけません。
この村の妻は決してその掟を破りません。
ある日村の女王が全員の前でこう言いました。「この村の夫の最低一人は浮気をしている。」
さて、この村に何が起こるでしょうか？
解いてみたら非常に面白かったので、自分の出した回答を晒しておきます。
では、挑戦。
以下では、
- 浮気経験のある夫 ＝ 黒夫
- 浮気経験のない夫 ＝ 白夫
とします。
まず、浮気していたのが1人だけだった場合について考えます。
妻は自分の夫以外の浮気がすぐにわかるので、
- 黒夫の妻( 1人) ⇒ 黒夫だとわかっている人数：0人
- 白夫の妻(99人) ⇒ 黒夫だとわかっている人数：1人
となります。
この状態で女王の宣告があれば、黒夫の妻はすぐに自分の夫が浮気をしていることがわかります。
他の99人が白なのは分かってるので、黒の可能性があるのは自分の夫だけですから。
よって、その日のうちに黒夫は殺されることになります。
次に、浮気していたのが2人だった場合について考えます。
- 黒夫の妻( 2人) ⇒ 黒夫だとわかっている人数：1人
- 白夫の妻(98人) ⇒ 黒夫だとわかっている人数：2人
となります。
この状態で女王の宣告があっても、黒夫の妻から見て浮気している人が1人いて、その人のことを言っている可能性もあるため、1日目は何も起こりません。
しかしもし黒夫が1人なら1日目に殺されるのはずなので、何も起こらないで2日目を迎えたことにより黒夫の妻にも浮気をしていたのが1人ではなかったことが分かります。
その他に浮気をしている可能性があるのは、自分が浮気をしているかどうか知ることができない、自分の夫以外あり得なくなります。
よって、2日目に2人の黒夫は殺されることなります。
浮気が3人だった場合には、
- 黒夫の妻( 3人) ⇒ 浮気したことがわかっている人数：2人
- 白夫の妻(97人) ⇒ 浮気したことがわかっている人数：3人
となります。
もし浮気をしているのが2人なら、2日目に殺人が行われるのは上で述べたとおりです。
しかし2日目に何もおきないので、浮気していたのが2人ではなかったことが黒夫の妻にもわかり、3日目に黒夫3人が殺されます。
･･･とまあ、ここまで書けば充分でしょう。
妻の立場からすると、n人の黒夫が見えている場合、自分の夫が白夫ならばn日目に殺人が起こることになります。
もしそれが起こらなければ自分の夫が浮気していることが分かるので、n+1日目に掟により夫を殺すことになります。
帰納法により何人でもこの法則が成り立つので、この村の場合は女王の宣告から100日目に全ての夫が殺されることになります。
面白いポイント
この問題、パッと聞いたときには「妻が既に知っている情報を女王が与えただけなんだから、何も起こらないんじゃね？」と考えそうです。
しかし、実は全妻に対して、
「もし浮気しているのが1人だけだったら、その日のうちに殺人が起こる」
という情報を与えたことになります。
この情報が引き金になって連鎖反応が起こり、結局全ての夫が殺されることになるとは、直感だけではなかなか分かりません。
コンピュータの問題に関わっている人なら、同じような事態に遭遇したことがあるのではないでしょうか？
直感では何も問題がなさそうに思えたプログラムの変更・仕様の変更などが、巡りめぐってトンでもない事態を引き起こしてしまったことは、誰でも一度は経験があると思います。
このテストは、そういった問題への対処できる論理思考力が備わっているのかを見るための問題なんだと思います。
おまけ
せっかくなので、黒夫達を救う方法について考えてみました。
妻は殺害が行われたかどうかでしか、自分の夫が黒夫かどうかを知ることができません。
とすれば、殺害を行えなくするか、殺害が行われても妻はそのことを知ることができなくなれば、この村に再び平和が訪れます。
案1．初日に、誰か1人死ぬ
これが発生したら村は救われます。死ぬのは夫でも妻でも構いません。
死んでしまった黒夫は殺せないですし、死んでしまえば黒夫を殺すこともできないからです。
ようするに、「もし浮気しているのが1人だけだったら、その日のうちに殺人が起こる」という条件を、殺人を行えなくすることで崩しています。
n日が経過するとn人が死んでくれないと連鎖が止まらないので、初日に発生するのがベストです。
でも、これを意図的にやろうとすると誰かを殺さないといけなくなります。
･･･なんかヤなので、もう少し平和的な手を考えてみます。
案2．初日に、一組の夫婦に旅に出てもらう
こちらの方がより平和的解決ですね。旅に出た夫妻が殺人を行ったかどうかがわからない状態を作り出しています。
ただし、旅先から帰ってきてしまうとまた連鎖が始まってしまうので2度と帰れませんが･･･。
あ、でもこれって白夫の夫婦を旅に出しても意味ないので、
- 自分たち夫婦が旅に出て行く組に選ばれた ⇒ 自分の夫は黒夫
となって、結局殺人が起こってしまうような･･･。じゃあ、
案3．村を2つに分けて、交流を絶つ
というのはどうかな？
あ、でもこれも2つに分けるときに、
- 片方が全員白夫だと成り立たなくなる ⇒ 自分たちの組に最低1人は黒夫がいる
ということになって、人数が減った分返って殺人が起こるタイミングを早めてしまうような･･･。ならば、
案4. 村を3つに分けて、交流を絶つ
で、なんとかならないかな？
自分たちの組が全員白夫でも成り立つので、連鎖が発生しなくなるはずです。
案5．案1, 案4のあわせ技。
初日に案4をやってしまえば、「黒夫は1人以上」という状況を保てます。
この状態で村の誰か1人が自然死するのを待てば、その後は元通りの村に戻れます。
村を分けるときに、「もし黒夫 or その妻が自然死したら、お互い連絡して元に戻る」という取り決めをしておけば良いのです。
(本当は誰が自然死しても良いのに、上のような取り決めにしないといけないのも、何気に面白いポイントだなぁ･･･。)
で、
回答の方は解いた後にGoogle先生に問い合わせて、どうやら合ってるらしいことが分かりました。
が、おまけの黒夫救出作戦の方は合ってるかどうかが分かりません。
もし間違っているとか、論理展開が甘いとかに気がついた方などおられましたら、突っ込んでいただけると幸いです。
