1.7 場合分けを使った証明

複雑な証明をいくつかの場合 (case) に分けるアプローチは一般的で有用な証明技法である。鮮やかな例を一つ示す。

人間が \(2\) 人いるとき、その \(2\) 人は互いに相手を知っているか、互いに相手を知らないかのどちらかだとしよう。人間の集まりに含まれる任意の \(2\) 人が互いに相手を知っているとき、その集まりを知人グループ (club)と呼ぶことにする。また、任意の \(2\) 人が互いに相手を知らないような人間の集まりを他人グループ (group of strangers) と呼ぶことにする。

証明 場合分けを使って証明する¹。\(6\) 人の人間の集まりから \(1\) 人を任意に選んで \(x\) とする。次の二つ場合を分けて考える:

このとき、二つの場合のいずれかが常に成り立つことを確認しなければならない²ものの、これは難しくない: \(x\) 以外の \(5\) 人を「\(x\) を知っている」と「\(x\) を知らない」の二つのグループに分けたとすれば、いずれかのグループには必ず \(3\) 人以上が含まれる。

• Case 1: \(x\) を知っている人が \(3\) 人以上いると仮定する。以降の議論はさらに二つの場合に分かれる:

  Case 1.1:

  \(x\) を知っている人の集まりに含まれる任意の \(2\) 人が互いに相手を知らないとき、その集まりは \(3\) 人以上の他人グループだから、示したい定理は成り立つ。

  Case 1.2:

  \(x\) を知っている人の集まりの中に互いに相手を知っている \(2\) 人が存在するとき、その \(2\) 人と \(x\) のグループは \(3\) 人の知人グループだから、示したい定理は成り立つ。

  よって Case 1 で定理は成り立つ。

• Case 2: \(x\) を知らない人が \(3\) 人以上いると仮定する。ここからの議論もさらに二つの場合に分かれる:

  Case 2.1:

  \(x\) を知らない人の集まりに含まれる任意の \(2\) 人が互いに相手を知っているとき、その集まりは \(3\) 人以上の知人グループだから、示したい定理が成り立つ。

  Case 2.2:

  \(x\) を知らない人の集まりの中に互いに相手を知らない \(2\) 人が存在するとき、その \(2\) 人と \(x\) のグループは \(3\) 人の他人グループだから、示したい定理は成り立つ。

  よって Case 2 でも定理は成り立つ。

以上より、全ての場合で定理は成り立つ。 ■