水無月ばけらのえび日記

bakera.jp > 水無月ばけらのえび日記 > 数学的帰納法を用いたパズル問題

数学的帰納法を用いたパズル問題

2011年11月5日(土曜日)

数学的帰納法を用いたパズル問題

公開: 2011年11月12日21時45分頃

大手IT企業の難解ななぞなぞのような採用試験問題 (it.slashdot.jp)」という話で紹介されていた問題。

100組の夫婦のいる村の男全員が不倫しています。どの妻も夫意外の男性が浮気していることは瞬時に分かってしまいます。しかし自分の夫の浮気には気がつきません。自分の夫が浮気していることを証明できる場合、妻は必ず夫をその日のうちに殺さなければなりません。村の女性はこの法を順守しなくてはなりません。ある日、村の女王が訪れ不倫している夫が最低でも1人いると告げます。どうなるでしょうか?

翻訳の問題なのでしょうが、文章が変だったり表現が曖昧なところがかなりありますね。アプローチの仕方として、「表現の曖昧さを指摘する」という方向に行くのは自然な流れでしょう。

しかしこの問題、元々は純粋に数学的なパズルとして考えられていたのではないでしょうか。せっかくなので、パズルとして解いてみたいと思います。曖昧な部分について、以下のような条件を加えて考えてみました。

こうするとパズルとして解けるようになってきます。以下、思考の過程。

方針

「100組の夫婦」というのはいかにも数が多いので、まず数が少ない場合を考えてみて、一般化できないか考えてみます。

夫婦が1組の場合

夫は村に一人しかいません。「不倫している夫が最低でも1人いる」という条件から、その夫が不倫していることが確定します。妻はその日のうちに夫を処刑します。

夫婦が2組の場合

夫婦をそれぞれA,Bとし、A妻の行動を考えます。

A妻はB夫の不倫を知っていますが、自身の夫であるA夫が不倫しているかどうかは分かりません。「不倫している夫が最低でも1人いる」という条件を与えられても、A夫の不倫は確定しません。A妻はB夫が不倫していることを知っていて、それだけで条件は満たされているからです。

問題は、「A夫は不倫しておらず、B夫だけが不倫している」のか、それとも「A夫、B夫共に不倫している」のか、ということです。後者であれば夫を処刑しなければなりません。

ここで、A妻は背理法を使って以下のように思考します。

  • まず、A夫が不倫していないと仮定する。
  • 仮定によりA夫が不倫していないのだから、B妻は「A夫が不倫していない」ことを確信する (夫以外の男性について、「不倫している→不倫していることがただちに分かる」が成立しているので、対偶の「不倫していることがただちには分からない→不倫していない」も成立)。
  • 「不倫している夫が最低でも1人いる」という条件から、B妻はB夫が不倫していることを確信する。
  • 従って、B妻は夫を今日中に処刑する。

つまりA妻は、「A夫が不倫していなければ、B夫が今日中に処刑されるはずである」と考えることになります。そこでA妻は1日様子を見ることにします。

しかし実際には、A夫は不倫をしているのですから、翌日になってもB夫は処刑されません。この時点で「A夫が不倫していない」という仮定が誤りだったことがわかります。すなわち、A妻は2日目になって夫の不倫を確信します。

結果として、A妻は2日目に夫を処刑することになります。

B妻もA妻と同じように思考して同じように行動することになりますので、1日目は互いに様子見で何も起きず、2日目になって夫2人が処刑されることになります。

夫婦が3組の場合

夫婦をそれぞれA,B,Cとし、A妻の行動を考えます。

A妻はB夫,C夫の不倫を知っていますが、自身の夫であるA夫が不倫しているかどうかは分かりません。

A妻は以下のように思考します。

  • まず、A夫が不倫していないと仮定する。
  • このとき、B妻、C妻の置かれている状況は、前述の「夫婦が2組の場合」と同じである (仮定のもと夫が浮気していないA夫婦が蚊帳の外に置かれて、残りの2夫婦B,Cについて「夫婦が2組の場合」と全く同じ状況が成立する)。
  • 従って、B妻、C妻は2日目に夫を処刑するはずである。

つまりA妻は、「A夫が不倫していなければ、B夫,C夫は2日目に処刑されるはずである」と考えることになります。そこでA妻は2日様子を見ることにします。

しかし実際には、A夫は不倫をしているのですから、2日目になってもB夫は処刑されません。この時点でA妻は夫の不倫を確信します。

結果として、A妻は3日目に夫を処刑することになります。

B妻もA妻と同様に思考して同様に行動しますので、2日目までは何も起きず、3日目になって夫3人が処刑されることになります。

夫婦がn組の場合

……と、ここまで考えると分かりますね。夫婦がn組の時、各妻は夫が不倫していないと仮定して、残りのn-1人の妻の行動を観察します。「夫婦がn-1組の場合に結論が出る日」を待って、その翌日に結論を出します。

また、n=1のときは、1日目に結論が出ます。

ということで、n組の夫婦がいるとき、n日目に結論が出て、全ての夫が処刑されることになります。

結論としては、夫婦が100組の場合、100日目に全ての夫が処刑されることになる、というのがパズル的な答えになるでしょう。

背理法、数学的帰納法といった考え方ができるかどうかを問う問題、というところでしょうか。

関連する話題: 数学 / 論理

最近の日記

関わった本など