グラフを利用する問題
有名問題で、握手した者同士を線で結んでいくとわかりやすい(グラフの利用)。
条件より、握手した回数は0~198の199通りあり、質問した相手と質問した人の配偶者の回答はすべて異なり、このいずれかとなる。
198人と握手した人は自分と自分の配偶者以外のすべての人と握手している。
198人と握手した人の配偶者以外は、少なくとも1人と握手しているので、握手した相手が0人となる人は198人と握手した人の配偶者となる。
以下、同様にしていく。
198 0
197 1
196 2
…………
100 98
質問した相手の回答は99以外となるから、質問者の配偶者が握手したのは99人となる。