6人ミーティング

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

うーんうーんとうなっていたのだが、全て列挙してみれば簡単に解けた。

  1. 全員が初対面の場合 => 「互いに初対面の３人組」が存在
  2. 5人が初対面,1人が互いに顔見知りの場合 => 「互いに初対面の３人組」が存在するが、状況としてありえないし、前提を満たさない。
  3. 4人が初対面,2人が互いに顔見知りの場合 => 「互いに初対面の３人組」が存在
  4. 3人が初対面,3人が互いに顔見知りの場合 => 「互いに初対面の３人組」が存在、「互いに会ったことのある３人組」が存在
  5. 2人が初対面,4人が互いに顔見知りの場合 => 「互いに会ったことのある３人組」が存在
  6. 1人が初対面,5人が互いに顔見知りの場合 => 「互いに会ったことのある３人組」が存在
  7. 6人が互いに顔見知りの場合 => 「互いに会ったことのある３人組」が存在

以上により、
「どの２人を取っても、初対面か会ったことがあるかのいずれかである」場合には、「互いに初対面の３人組」か「互いに会ったことのある３人組」のどちらかは存在する。

証明終