§B4.21競技数学：組合せ・複雑な場合の数

最終更新

本記事では、鳩の巣原理、包除原理、二通りの数え上げ、不変量、極端原理、グラフとしての表現を組み合わせる問題を扱います。各技法の一般形は、それぞれの技法を主題とする記事で扱います。とくに、鳩の巣原理そのものは§B4.2 鳩の巣原理で、何を箱とみなすかという設計は§C5.1 鳩の巣原理の応用で扱います。

1 グラフと鳩の巣原理

定理 1.1 (6人問題). 6人の集団には、互いに知り合いである3人、または互いに知らない3人が存在します。

証明. 人を頂点とし、知り合いの二人を辺で結びます。一人PPを選ぶと、残り5人はPPと知り合いであるか、知らないかの二種類に分かれます。鳩の巣原理により、少なくとも3人が同じ種類です。

PPと知り合いである3人をA,B,CA,B,Cとします。A,B,CA,B,Cの中に知り合いの二人がいれば、その二人とPPが互いに知り合いです。知り合いの二人がいなければ、A,B,CA,B,Cが互いに知り合いでない3人です。PPと知らない3人の場合も、知り合いと知らないを入れ替えると同じ議論が成り立ちます。▨

上の6人問題の証明では、関係をグラフで表し、頂点PPに接続する5本の関係を二種類へ分けて、鳩の巣原理を用いています。

2 包除原理と二通りの数え上げ

例 2.1. 4人へ4通の手紙を一通ずつ配り、少なくとも一人が自分宛てを受け取る配り方を数えます。全24通りから完全順列9通りを引くと15通りです。一方、人iiが自分宛てを受け取る集合をAiA_iとして包除原理を用いると、

4⋅3!−4C2⋅2!+4C3⋅1!−1=24−12+4−1=154\cdot3!-{}_4C_2\cdot2!+{}_4C_3\cdot1!-1=24-12+4-1=15

通りです。補集合による数え方と包除原理による数え方が一致します。

3 彩色による不変量

例 3.1. 8行8列の市松模様の盤面から、同じ色である対角の二隅を除きます。残る62マスを、隣り合う二マスを覆うドミノ31枚で敷き詰めることはできません。

各ドミノは白いマスと黒いマスを一つずつ覆うので、どの段階でも覆った白いマスと黒いマスの個数は等しいという性質が保たれます。一方、もとの盤面には各色32マスがあり、同じ色の二隅を除くと、一方が30マス、他方が32マスです。したがって、全マスを覆うことはできません。

盤面を彩色して、ドミノを置いても保たれる個数の差を見つけると、すべての配置を列挙することなく不可能性を示すことができます。

4 極端原理とグラフ

定理 4.1. 任意のnn人について、各二人の試合に引き分けがなく勝者が一人だけ決まるとします。このとき、選手をv1,…,vnv_1,\ldots,v_nと並べ、各iiでviv_iがvi+1v_{i+1}に勝つようにすることができます。

証明.v1v_1がv2v_2に勝ち、v2v_2がv3v_3に勝つというように、隣接する勝敗の向きがそろう道のうち、選手数が最大のものをv1,…,vrv_1,\ldots,v_rとします。道に含まれない選手wwがいると仮定します。

wwがv1v_1に勝つならば、wwを先頭へ置いて道を長くすることができます。vrv_rがwwに勝つならば、wwを末尾へ置いて道を長くすることができます。したがって最大性から、v1v_1はwwに勝ち、wwはvrv_rに勝ちます。wwが勝つ最初のvjv_jを取るとj≥2j\ge2であり、jjの最小性からvj−1v_{j-1}はwwに勝ちます。よってvj−1v_{j-1}とvjv_jの間へwwを挿入して道を長くすることができ、最大性に反します。

したがって最大の道は全選手を含みます。▨

上のトーナメントの問題の証明では、勝敗を有向グラフとして表し、極端原理に従って、勝敗の向きがそろう道のうち選手数が最大のものを選んでいます。最大であると仮定した道をさらに長くする構成により、矛盾が得られます。

5 演習

問題 5.1.定理 1.1の証明で、鳩の巣原理へ渡した対象と二種類の箱を明示せよ。

解答.

対象は、選んだ一人PPと残りの5人それぞれとの関係5本である。箱は「PPと知り合い」と「PPと知らない」の二種類である。5>2⋅25>2\cdot2なので、§B4.2 定理 1.3をr=2r=2として適用すると、一方の箱に3本以上の関係が入る。したがって、PPと知り合いである3人、またはPPと知らない3人が存在する。▨

問題 5.2. 5人へ宛名の異なる5通の手紙を一通ずつ配るとき、少なくとも一人が自分宛ての手紙を受け取る配り方の数を、包除原理で求めよ。

解答.

人iiが自分宛ての手紙を受け取る配り方の集合をAiA_iとする（i=1,…,5i=1,\ldots,5）。指定したkk人が自分宛ての手紙を受け取る配り方は、残りの5−k5-k通を残りの5−k5-k人へ配る方法の数(5−k)!(5-k)!通であり、kk人の指定の仕方は5Ck{}_5C_k通である。したがって、§B4.4 定理 1.1により、

∣⋃i=15Ai∣=5⋅4!−5C2⋅3!+5C3⋅2!−5C4⋅1!+5C5⋅0!=120−60+20−5+1=76\left|\bigcup_{i=1}^{5}A_i\right| =5\cdot4!-{}_{5}C_2\cdot3!+{}_{5}C_3\cdot2!-{}_{5}C_4\cdot1!+{}_{5}C_5\cdot0! =120-60+20-5+1=76

であり、求める配り方は76通りである。§B4.4 例 2.1の式から得られる完全順列の個数D5=44D_5=44を全体の5!=1205!=120通りから引いても、120−44=76120-44=76通りとなり、二つの数え方は一致する。▨

問題 5.3.例 3.1の、二隅を除いた盤面について、ドミノを置くたびに保たれる量と、最初から一致しない二つの個数を説明せよ。

解答.

保たれる量は、ドミノで覆った白いマスの個数から黒いマスの個数を引いた差である。各ドミノは白いマスと黒いマスを一つずつ覆うので、ドミノを1枚置くたびに二つの個数はともに1ずつ増え、差は0のまま保たれる。一方、除いた二隅の色を白とすると、残る盤面の白いマスは30個、黒いマスは32個である。全マスを覆ったとすると、覆った白いマスは30個、黒いマスは32個になり、差は−2-2である。差が0に保たれることと両立しないので、全マスを覆うことはできない。除いた二隅の色が黒の場合も、白と黒を入れ替えると同じ議論が成り立つ。▨

問題 5.4.定理 1.1、例 2.1、例 3.1、定理 4.1の四つの問題で用いた技法を、鳩の巣、包除、二通りの数え上げ、不変量、極端原理、グラフの六語から選べ。一つの問題で複数の技法を用いている場合は、すべて挙げよ。

解答.

定理 1.1の証明では、人を頂点とし知り合いの二人を辺で結ぶグラフを用い、PPとの関係5本に鳩の巣原理を適用している。したがって、技法は鳩の巣とグラフである。例 2.1では、包除原理による計算と、補集合による計算の二通りで同じ個数を数えている。したがって、技法は包除と二通りの数え上げである。例 3.1では、覆った白いマスと黒いマスの個数の差が保たれることを用いている。したがって、技法は不変量である。定理 4.1の証明では、勝敗を有向グラフとして表し、勝敗の向きがそろう道のうち選手数が最大のものを選んでいる。したがって、技法は極端原理とグラフである。▨

前提記事