17人で3つの話題

漫画「数学ゴールデン」の1巻に次のような問題が出てくる。それを解いてみた。

「17人それぞれが他の全員と互いに手紙のやりとりをしている。

　その手紙では3つの話題のみがやりとりされている。

　そして、同じ2人組の間でなされる話題は常に同じ1つのやりとりである。

　このとき、互いに同じ話題の手紙のやりとりをした3人組が存在することを証明せよ」

　(証明)

　　3つの話題をA、B、Cとする。

　　17人のうち1人をxとして、そのxと残りの16人との手紙のやりとりを考える。

　　天井関数をceil()で表す。

　　ceil(16/3)=6人以上のやりとりをする話題が1つは存在する。その話題をAとする。

　　その6人以上の中の2人が話題Aで手紙をやりとりしていたら、xとその2人が求める3人組である。

　　その6人以上の中での手紙のやりとりが話題Aではされていないとする。

　　その6人以上の中の1人をyとして、そのyと残りの5人以上との手紙のやりとりを考える。

　　ceil(5/2)=3人以上やりとりする話題が1つは存在する。その話題をBとする。

　　その3人以上の中の2人が話題Bでやりとりしていたら、yとその2人が求める3人組である。

　　その3人以上の中での手紙のやりとりが話題Bでされていないとする(もちろん話題Aでもない)。

　　すると、その3人以上の中での手紙のやりとりは話題Cでのみされているので、任意の3人を選ぶと話題Cで手紙のやりとりをしている3人組となる。

　　よって、必ず、互いに同じ話題の手紙のやりとりをした3人組が存在する。(証明終わり)