握手問題のこたえ

　以前の記事で紹介した、「握手問題」。まずはその内容のおさらいから。

　１０組の夫婦が集まるパーティーがあった。その会場では参加者の間で握手がなされた。
　どの参加者も、自分自身とは握手はしていない。
　どの参加者も、自分の配偶者とは握手はしていない。
　どの参加者も、同じ相手と２回以上の握手はしていない。
　パーティー終了後、参加者の１人のＡさんは、自分以外の１９人に対して「何回握手しましたか？」と質問した。すると、１９人の言った回数は全て異なっていた。

　この時、Ａさんの配偶者の握手の回数は何回か。

　実は、この解答をきちんと書くのは難しい。ただ、内容をわかっていただければということで、書ける範囲で説明したいと思う。

１）１９人の言った回数は？
　１人が、握手し得る最多回数は何回か。参加者２０人から、自分自身と配偶者の２人を除いた、１８回。一方、最少は０回。握手の回数は当然整数なので、最高でも０から１８までの１９通りのパターンしかない。
　また、「１９人の言った回数は全て異なっていた」ということは、１９人は異なる１９通りの答え（回数）を言ったことになる。
　つまり、最高でも１９通りしかないのに１９人が異なる答えをしたということになるので、以上から、「０回」「１回」「２回」…「１７回」「１８回」が全て１人ずついることがわかる。それ以外のパターンはあり得ない。

２）「０回の人」の配偶者は何回か
　０回の人は、誰とも握手をしていない。もし、０回の人と１８回の人が夫婦でないとすると、矛盾が生じる。なぜなら、１８回の人は自分自身と自分の配偶者以外、残り１８人の全員と握手をしているので、この１８人の中に０回の人がいるはずはない。
　よって、０回の人と１８回の人は夫婦である。

３）「１回の人」の配偶者は何回か
　１回の人は、２）の１８回の人と握手をしたのが全てで、それ以外の人とは握手をしていない。
　一方、１７回の人は、「自分自身と自分の配偶者と２）の０回の人」以外の１７人全員と握手をしている。
　２）の結論と合わせると、１回の人と１７回の人が夫婦でないとすると矛盾が生じる。
　よって、１回の人と１７回の人は夫婦である。

４）これを繰り返していく
　以下同様にして、２回と１６回が夫婦、というように組み合わせていくことができる。すると、９組の夫婦の組み合わせができて、残るのは「９回」の人である。
　１９人の中で、夫婦でないのはＡさんの配偶者だけなので、正解は９回。

追伸：最後まで読んでいただいた方がどれほどいらっしゃるか、心配だ。