存在性証明としての鳩の巣原理

ウィキペディア小見出し辞書

存在性証明としての鳩の巣原理

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/06/25 08:26 UTC 版)

「鳩の巣原理」の記事における「存在性証明としての鳩の巣原理」の解説

前述した「ロンドンには、同じ本数の髪の毛を持った少なくとも2人の人間が存在する」ということの証明の面白いところは、同じ本数の髪の毛の人が存在することを証明しているにもかかわらず、具体的にどの2人が同じ本数の髪の毛を持つのかは分からないということである。鳩の巣原理を使った証明にはこのような特徴をもつものが多く、何らかの性質を満たすものが存在することを証明するにもかかわらず、どれがその性質を満たすのかについては何も分からない。もちろん100万人以上いるロンドン市民の髪の毛の本数を全員チェックすればどの２人が同じ本数の髪の毛を持つのか分かるが、このような非効率的なことをしなくても定理が証明できるのが鳩の巣原理の利点である(チェックが多項式時間でできないにもかかわらず、鳩の巣原理により存在性のみが言える例もある)。 この特徴のため、鳩の巣原理は定理を証明する強力な道具になる。実際、無限がからんだ場合、鳩の巣原理を使わないとおよそ証明できない命題を証明できる場合がある。前述の例を少しだけ改変して、「30万以上の人口を持つ任意の都市Xに対し、Xには同じ本数の髪の毛を持った少なくとも2人の人間が存在する」という命題を考える。世界にあるそのような都市の数が有限であれば、全ての都市にいる全ての人間の髪の毛の本数を数えることで上述の命題の真偽がチェックできるが、そのような都市の数が無限であれば、全ての都市についてチェックするのは原理的に不可能である。しかし鳩の巣原理を使えば、たとえそのような都市の数が無限であってもこの定理が真であることを一瞬にして証明できる。