本記事は、鳩の巣原理、包除原理、二通りの数え上げ、不変量、極端原理、グラフとしての表現を組み合わせる問題を扱います。各技法の一般形は、それぞれの主担当記事が扱います。とくに、鳩の巣原理そのものは「鳩の巣原理」が、何を箱とみなすかという設計は「鳩の巣原理の応用」が扱います。
1 グラフと鳩の巣原理
定理 1.1 (6人問題). 6人の集団には、互いに知り合いである3人、または互いに知らない3人が存在します。
証明. 人を頂点とし、知り合いの二人を辺で結びます。一人を選ぶと、残り5人はと知り合いであるか、知らないかの二種類に分かれます。鳩の巣原理により、少なくとも3人が同じ種類です。
と知り合いである3人をとします。の中に知り合いの二人がいれば、その二人とが互いに知り合いです。知り合いの二人がいなければ、が互いに知り合いでない3人です。と知らない3人の場合も、知り合いと知らないを入れ替えると同じ議論が成り立ちます。▨
この証明は、関係をグラフで表し、頂点に接続する5本の関係を二種類へ分け、鳩の巣原理を用いています。
2 包除原理と二通りの数え上げ
例 2.1 (禁止位置をもつ順列). 4人へ4通の手紙を一通ずつ配り、少なくとも一人が自分宛てを受け取る配り方を数えます。全24通りから完全順列9通りを引くと15通りです。一方、人が自分宛てを受け取る集合をとして包除原理を用いると、
通りです。補集合による数え方と包除原理による数え方が一致します。
3 彩色による不変量
例 3.1 (二隅を除いた盤面). 8行8列の市松模様の盤面から、同じ色である対角の二隅を除きます。残る62マスを、隣り合う二マスを覆うドミノ31枚で敷き詰めることはできません。
各ドミノは白いマスと黒いマスを一つずつ覆うので、どの段階でも覆った白いマスと黒いマスの個数は等しいという性質が保たれます。一方、もとの盤面には各色32マスがあり、同じ色の二隅を除くと、一方が30マス、他方が32マスです。したがって、全マスを覆うことはできません。
彩色によって保たれる個数の差を見つけると、すべての配置を列挙せずに不可能性を示すことができます。
4 極端原理とグラフ
定理 4.1 (トーナメントの有向道). 任意の人について、各二人の試合に引き分けがなく勝者が一人だけ決まるとします。このとき、選手をと並べ、各でがに勝つようにすることができます。
証明.がに勝ち、がに勝つというように、隣接する勝敗の向きがそろう道のうち、選手数が最大のものをとします。道に含まれない選手がいると仮定します。
がに勝つならば、を先頭へ置いて道を長くすることができます。がに勝つならば、を末尾へ置いて道を長くすることができます。したがって最大性から、はに勝ち、はに勝ちます。が勝つ最初のを取るとであり、の最小性からはに勝ちます。よってとの間へを挿入して道を長くすることができ、最大性に反します。
したがって最大の道は全選手を含みます。▨
ここでは、勝敗を有向グラフとして表し、条件を満たす道のうち選手数が最大のものを選ぶ極端原理を用いています。最大であると仮定した対象をさらに長くする構成が矛盾を与えます。
5 演習
- 6人問題の証明で、鳩の巣原理へ渡した対象と二種類の箱を明示します。
- 5人への手紙について、少なくとも一人が自分宛てを受け取る配り方を包除原理で求めます。
- 二隅を除いた盤面で、ドミノを置くたびに保たれる量と、最初から一致しない二つの個数を説明します。
- 上の四問題が用いた技法を、鳩の巣、包除、二通りの数え上げ、不変量、極端原理、グラフの六語から選び、複数ある場合はすべて挙げます。
1では、対象はと残りの各人との5本の関係であり、箱は「知り合い」と「知らない」の二種類です。2は包除原理から
通りです。3では、覆った白マス数と黒マス数の差が0に保たれますが、残る盤面の二色の個数は30と32です。4では、6人問題が鳩の巣とグラフ、禁止位置をもつ順列が包除と二通りの数え上げ、盤面が不変量、トーナメントが極端原理とグラフを用います。