パーティー問題

　パーティーとは出会いの場である。パーティーで全員楽しくすごすためには、仲間はずれを作らないというところに鍵がある。全員が仲のよい内輪のパーティもいいだろうし、逆に全員が初対面という合コンの様な状況も良いのではないかと思う。まずいのは、少数で仲のよい、あるいは少数で他人のグループができてしまう状況や、グループが分裂してしまう状況だ。

例えば3人のパーティーで一番良いのは3人とも全員知り合いか、全員とも初対面に限る。一番まずいのは、2人だけ知り合いでもう一人は全く他人という状況（そんなパーティーはないだろうが）。これでは一人だけ話に参加できずに寂しい状況になってしまう。もうひとつは3人の中のAだけはB,Cと知り合いで、B,C同士は他人という状況。結婚式なんかは往々にしてそんな状況だが、これも良くない。

　そこでこんな問題を考える。
　「3人が全員知り合い、または3人が全員他人という組が必ず存在するためには最低何人の客をパーティーに招待すればよいか？」

　3人では無理なことは先ほどいった。AとBが知り合いで、Cは誰とも知り合いでない、あるいはAとだけ知り合いという場合が考えられるからである。4人ではどうか？A,Bが知り合い、C,Dが知り合いという具合に分裂の状況があるのでこれもダメである。では5人ではどうか？実はこれもダメなのである。面倒なので図で説明するが、人を点で表し、知り合いの場合には実線で結び、知り合いで無い場合には点線で結ぶ。
　

⇒

　というわけで右のような星型の状況を考えれば、どの3人も全員知り合い、あるいは全員他人の状況にはなっていない。つまり、どの3点を取ってきても実線の３角形、あるいは点線の３角形が作れない。では６人ならどうか？6人の場合、全員が二人以下しか知り合いを持たないと、知り合いの組が少なすぎて必ず3人が全員知り合いでない組ができてしまう。ということは、6人のうち少なくとも一人は他の3人と知り合いの人物がいるはずである。そいつを頂点にして考えよう。

⇒

頂点の人物をAとすると、B,C,Dという3人と実線で結ばれる。このとき、B,Cが知り合いだとA,B,Cで実線の３角形ができるため、B,Cは知り合いでない。同様にC,Dも知り合いでない。残りはB.Dの関係だが、これは赤線の箇所であるが、これは実線であればABDで実線の３角形ができ、点線ならBCDで点線の３角形ができてしまうので、どうやっても３人で全員知り合い、または全員他人の組が必ずできる。よって、6人呼べばＯＫなのである。

　ではもっと発展して4人の互いに知り合い、または全員他人の組ができるために必要なのは最低何人だろう？5人では？6人では？