google入社試験問題

　昨日ていおうさんちで遊んでいるときにグーグルの入社問題をみんなで考えておりました。

　そんなときに気になったのがこちらの問題


　この村には100組の夫婦がいて、夫は全員浮気しています。
妻は全員、自分の夫以外が浮気していることは知っています。
そしてこの村の掟では浮気や姦通は許されていません。
また、どの妻も自分の夫が浮気していると知ればすぐに自分の夫を殺すという掟があります。
この村の女達は掟には背きません。
ある日、村の女王が言いました。この村には浮気をしている男が少なくとも1人はいる。
さて、この村に何が起きますか？



　ヤフー知恵袋ではみんな違ったベストアンサーを出していてカオスだったので俺もじぶんなりに考えてみました。


　まず基本的な基礎知識として数学的帰納法を使用したいと思います。高校のころ習いましたね。


　特定の事象に対して変数が0のときとnの時に成立することを利用してn+1の時に成立することを証明できればあらゆる変数に対してその事象を成立させることが証明されます。


　これは定義なのでちょっといんちきくさいですがブラックボックス的な使い方をさせてもらいます。



　ここではその変数を「自分以外の夫婦の数」としましょう。

　村に1組しか夫婦がいなければ変数は0、100組いるなら99ですね。



　では変数が0の場合・・・一組しかいない夫婦に対して一人浮気しているといえば確実にその夫が殺されます。

　
　変数1の場合・・・つまり２組の夫婦がいる場合ではとりあえずは誰も殺されない。それはどちらの妻もほかの妻の夫が浮気をしている犯人だと思っているから・・・という真理に二人ともたどり着いてしまい２人の夫が殺される。

　わかりやすく説明するために視点を一人の妻の視点にしてみると

　前提：私は自分以外の夫、つまりとなりの夫の浮気を知っているが自分の夫が浮気しているかどうかは知らない。

　1：私の夫は浮気をしていないということをとなりの夫婦の妻も知っているならとなりの妻は夫を殺すはずなので自分の夫の無実はとなりの夫の死によって証明される。とりあえず保留。

　2：でもとなりの夫が殺されないということはとなりの妻が私の夫の浮気を知っていて「1」と同じ考えにいたっている。

　3：つまり私の夫「も」浮気をしている。

　といった感じでしばらくしても誰も殺されないと２人の夫が殺されます。



　変数2の場合・・・これを変数1の場合を使って証明することによって数学的帰納法が成立する。３組の夫婦がいた場合では・・・

　ちなみに勘のいいみなさんはもうお気づきですね？

　ここでも妻の一人称にたって考えましょう。

　前提：私はほかの２人の夫の浮気を知っている。

　1：ほかの２組の夫婦の夫は浮気をしているので自分の夫が浮気をしていなくてほかの２組の夫婦の妻も私の夫の誠実を知っていると信じたい。

　2：本当に私の夫が誠実でほかの２組の妻もそう知っているなら「1」の段階で残りほ２人の状況は変数1、つまり２組の夫婦がいた場合に収束するはず、つまり私の夫が誠実なら残りの２組の夫婦の夫は２人とも殺されるはず。

　3：でもだれも殺されない

　4：つまり私の夫「も」浮気をしている

　という真理に全員がたどりつき３人の夫が殺されます。


　もうおわかりですね？

　たとえ4組いても自分の夫が誠実ならほかの３組は上記のように全滅してるはずですよね。でも全滅していない・・・つまり自分の夫も浮気してる。→4組全滅。


　5組いても自分の夫が誠実ならほかの４組は上記のように全滅してるはず。なのに全滅しないから自分の夫も浮気してる→５組全滅。


　以降無限ループ。


　これにて帰納法による証明完了。結論は最終的には全員の夫が殺される。

　まあ単純な話としては100人の妻が集まって情報のやりとり（密告し合えば）全員の夫が殺されますよね。でもこういった問題ではそういう屁理屈は考えないのがセオリー・・・のはずなのですが実は各自で自分の夫を殺すか殺さないかというシグナルによって情報のやりとりができてしまう・・・なんかゾクっとしますがそういうところに気づけるかどうかがポイントだったんでしょうかね。



　寝覚めすっきりで考えたところ結構納得のいく答えが出ました、どう思いますかていおうさんリア充さん。




　トップレガシーのレポはまた後ほど。