ホーム >> 組合せ >> 社交的か非社交的な人が必ずいるパーティ
hide or visible

問題の説明

グラフ理論の問題ですが,特別な知識は必要ありません.以下では,状況を簡略化するために,人を点で表し,『$2$ 人が互いに知り合いである』という状況を, $2$ 点を線分で結ぶことで表します.同様に,『$2$ 人が互いに知り合いでない』という状況を,$2$ 点を線分で結ばないことで表します.


5人以上であること

参加者が $5$ 人以上であることは容易にわかります.なぜならもし,参加者が $4$ 人以下ならば,どの参加者も知り合いの数が $3$ 人以下で,さらに知り合いでない人の数も $3$ 人以下なので,問題の条件を満たすような人物はいません.

8人以上いれば条件を満たす

最少人数を聞かれているので,ここの考察は解答を求めるだけなら必要ないかもしれませんが,念のためしておきます.
参加者が $8$ 人以上であれば条件を満たすことがわかります.もし,参加者が $8$ 人以上ならば,ある参加者一人に注目すると,その人の知り合いと知り合いでない人の数は合わせて $7$ 人以上です.$7$ より大きい数をどのように $2$ つの自然数に分けても,どちらか一方は $4$ 以上になります.ゆえに,$8$ 人以上いれば条件を満たします.さて $8$ 人がこの問題の答えでしょうか.それを言うためには,$7$ 人以下で条件を満たさないことを示さなければなりません.参加者が $7$ 人以下の場合を見てみましょう.

参加者が5人の場合

参加者が $5$ 人の場合,参加者同士がたとえば次のような交友関係だったとします.

このとき,どの参加者の知り合いの数も $2$ 人で知り合いでない人の数は $3$ 人ですから,条件を満たしません.要するに,どの参加者も,知り合いの数と知り合いでない人の数の大きい方が $3$ 以下にできるような交友関係が見つかれば,問題の条件を満たさないようにできるということです.

参加者が6人の場合

参加者が $6$ 人の場合も,参加者がたとえば次のような交友関係だった場合,条件を満たしません.

参加者が7人の場合

最後に,参加者が $7$ 人の場合を考えます.実は,参加者が $7$ 人の場合は条件を常に満たします.つまり,どのような交友関係であったとしても,『知り合いが $4$ 人以上いるか,または知り合いでない人が $4$ 人以上いる』ような人が確実に存在します.以下,それを説明します.

背理法を用います.いま,どの参加者についても,知り合いの数と知り合いでない人の数のどちらも $3$ 人以下だったとします.全参加者の数は $7$ 人なので,どの参加者についても,知り合いの数と知り合いでない人の数の和は $6$ 人です.したがって,どの参加者も知り合いの数がちょうど $3$ 人ということになります.しかし,グラフの線分の数に注目すると,$\frac{7\times 3}{2}$ となって,これは整数でないので,このようなことはありえません.よって,『知り合いが $4$ 人以上いるか,または知り合いでない人が $4$ 人以上いる』ような人が確実に存在します.

以上より,求める答えは $7$人ということがわかります.


文章で考えるとわかりにくいですが,グラフに落としこんで考えるとわかりやすいですね.