@kyanny's blog

My life. Opinions are my own.

迷路じゃないほうの問題やってみた

 6人でミーティングをする。どの2人を取っても、初対面か会ったことがあるかのいずれかである。このとき、「互いに初対面の3人組」か「互いに会ったことのある3人組」のどちらかは存在することを証明せよ

問題公開のあとの反応: 人生を書き換える者すらいた。

これ考えてみた。下の図で上下白のペアが「互いに初対面」白黒のペアが「互いに会ったことがある」とする。

白黒両方が二つ以下になることはないので、『「互いに初対面の三人組」か「互いに会ったことのある三人組」のどちらかは存在する』といえる。証明終わり。

・・・で合ってるでしょうか。。え、迷路?解けませんでしたが何か?