MathLabs

競技数学と問題解決

オリンピック組合せ論

数え上げ、彩色、組合せゲームに関する競技問題を、巧妙な構成で解く分野。

直観同じものを二通りに数える

生徒全員がパートナーと踊るか一人で立っている学校のダンスパーティーを想像してほしい。「踊っているペアの数を2倍」と数えても「踊っている生徒は何人か」と数えても同じ合計になる——各ペアがそれぞれの側にちょうど一人の踊り手を寄与するからだ。この技、同じ対象の集合を二通りの異なる方法で数えて二つの結果を等しいと置くことを二重数え上げと呼び、オリンピック組合せ論で最も鋭い道具の一つである:明示的な公式を作る代わりに、同じ量の二つの正直な記述を見つければ恒等式や不等式がただで得られる。

5個ずつ2グループに分けた10頂点上の二部グラフのネットワーク図。すべての辺がグループ間を渡り、グループ内には辺がない。
5個ずつ2グループに分けた10頂点上の二部ネットワーク:すべての辺がグループ間を渡るため、3頂点が三角形を作ることは決してなく、辺数はちょうどMantelの限界 2525 に達する。

中高二重数え上げと握手補題

定義: 二重数え上げ

二重数え上げの議論は、ある集合(しばしば対の集合、または二種類の対象間の接続)の大きさを二通りの方法で計算し、二つの式を等しいと置く。グラフ G=(V,E)G=(V,E) では、古典的な例として「頂点-辺接続」の集合(vv が ee の端点である対 (v,e)(v,e))を数える:各辺はちょうど2つの接続を寄与し、各頂点 vv は deg⁡(v)\deg(v) 個の接続を寄与する。

∑v∈Vdeg⁡(v)=2∣E∣\sum_{v \in V} \deg(v) = 2|E|

ここで VV は頂点集合、EE は辺集合、deg⁡(v)\deg(v) は頂点 vv に接する辺の数である。左辺は頂点ごとに接続を数え、右辺は同じ接続を辺ごとに数える(1辺あたり2個)。両辺が全く同じ集合を数えているため、直ちに得られる系として奇数次数の頂点の個数は常に偶数である——これはオリンピックのグラフ問題で絶えず使われる事実である。

∑k=0n(nk)2=(2nn)\sum_{k=0}^n \binom{n}{k}^2 = \binom{2n}{n}

この二番目の恒等式は、nn 人の男子と nn 人の女子からなる集団から nn 人を選ぶ方法の数を二通りに数えることから得られる(以下で完全に証明する):直接には (2nn)\binom{2n}{n} であり、選んだ男子の人数で分けると ∑k=0n(nk)2\sum_{k=0}^n \binom{n}{k}^2 である。この同じ二通りに数えるという発想は極値問題も導く:正確な量を数える代わりに、関連する構造を数える二つの方法を比較して上から評価する、以下のTurán型定理のように。

オリンピック組合せ論の三つの中核技法
技法主な考え方適用例
二重数え上げ同じ集合を二通りに数えて結果を等しいと置く∑k=0n(nk)2=(2nn)\sum_{k=0}^n \binom{n}{k}^2 = \binom{2n}{n}
Turán型極値評価禁止された部分構造を避ける辺・集合の数を評価する三角形を含まない GG に対し e(G)≤⌊n2/4⌋e(G) \le \lfloor n^2/4 \rfloor
Combinatorial Nullstellensatz巧妙に構成した多項式の非零係数が格子上の非零点の存在を強制する零和または虹色部分構造の存在証明

大学二つの礎となる定理

定理: Turánの定理、三角形を含まない場合(Mantelの定理)

nn 頂点のグラフ GG が三角形(K3K_3)を含まないならば、e(G)≤⌊n2/4⌋e(G) \le \lfloor n^2/4 \rfloor であり、この限界は大きさ ⌊n/2⌋\lfloor n/2 \rfloor と ⌈n/2⌉\lceil n/2 \rceil の部分を持つ完全二部グラフによってちょうど達成される。

なぜ正しいのか?

三角形を含まないグラフでは、隣接する二頂点が共通の隣接点を持つことはできないため、両者の次数の和は nn で厳しく抑えられる。頂点をほぼ等しい二つのグループに分けてすべての交差対を結ぶと、この上限が至る所で同時に飽和するため、均衡の取れた完全二部グラフが極値例となる。

証明

nn について帰納法を用いる。n≤2n \le 2 では ⌊n2/4⌋≥0\lfloor n^2/4 \rfloor \ge 0 であり、高々2頂点のグラフは高々1辺しか持たないため主張は自明である。

nn 未満の頂点数を持つすべての三角形を含まないグラフで主張が成り立つと仮定し、GG を nn 頂点上の三角形を含まないグラフとする。GG に辺がなければ限界は自明に成り立つので、GG が辺 uvuv を持つと仮定する。GG は三角形を含まないため、uu と vv は共通の隣接点を持たない、すなわち N(u)∩N(v)=∅N(u) \cap N(v) = \varnothing である。

N(u)N(u) と N(v)N(v) は nn 頂点集合の互いに素な部分集合であるから、deg⁡(u)+deg⁡(v)=∣N(u)∣+∣N(v)∣=∣N(u)∪N(v)∣≤n\deg(u)+\deg(v) = |N(u)|+|N(v)| = |N(u) \cup N(v)| \le n が成り立つ。

GG から uu と vv を取り除いて n−2n-2 頂点上の三角形を含まないグラフ G′G' を得る。GG の各辺は辺 uvuv であるか、uu または vv から残りへの辺であるか、G′G' の辺であるかのいずれかであり、注意深く数えると e(G)=e(G′)+deg⁡(u)+deg⁡(v)−1e(G) = e(G') + \deg(u) + \deg(v) - 1 が成り立つ(この −1-1 は辺 uvuv が deg⁡(u)+deg⁡(v)\deg(u)+\deg(v) の中で一度数えられるが G′G' の辺ではないことを補正する)。

帰納法の仮定より e(G′)≤⌊(n−2)2/4⌋e(G') \le \lfloor (n-2)^2/4 \rfloor なので、e(G)≤⌊(n−2)2/4⌋+n−1e(G) \le \lfloor (n-2)^2/4 \rfloor + n - 1 である。直接計算すると (n−2)2/4+n−1=n2/4−n+1+n−1=n2/4(n-2)^2/4 + n - 1 = n^2/4 - n + 1 + n - 1 = n^2/4 となり、nn の偶奇を個別に確認すると ⌊(n−2)2/4⌋+n−1≤⌊n2/4⌋\lfloor (n-2)^2/4 \rfloor + n - 1 \le \lfloor n^2/4 \rfloor が正確に成り立つ。したがって e(G)≤⌊n2/4⌋e(G) \le \lfloor n^2/4 \rfloor となり、帰納法が完了する。

極値の場合、大きさ ⌊n/2⌋\lfloor n/2 \rfloor と ⌈n/2⌉\lceil n/2 \rceil の部分を持つ完全二部グラフは三角形を含まず(三角形には同じ部分内の辺が必要だがそのような辺は存在しない)、ちょうど ⌊n/2⌋⋅⌈n/2⌉=⌊n2/4⌋\lfloor n/2 \rfloor \cdot \lceil n/2 \rceil = \lfloor n^2/4 \rfloor 本の辺を持つため、この限界は最良である。

定理: 二項恒等式の二重数え上げによる証明

任意の整数 n≥0n \ge 0 に対して ∑k=0n(nk)2=(2nn)\sum_{k=0}^{n} \binom{n}{k}^2 = \binom{2n}{n}。

なぜ正しいのか?

両辺は同じもの——2n2n 人から nn 人を選ぶ方法の数——を数えているため、二項係数の代数的な変形は一切不要で、一つの選択過程を二つの異なる順序で丁寧に記述するだけでよい。

証明

nn 人の男子と nn 人の女子からなる 2n2n 人の集合を考える。この 2n2n 人からちょうど nn 人の委員会を選ぶ方法の数を二通りに数える。

直接には、定義よりこの数は (2nn)\binom{2n}{n} である。単に 2n2n 個から nn 個を選んでいるだけだからである。

別の方法として、すべての有効な委員会を含まれる男子の人数で分類する。委員会がちょうど kk 人の男子を含む場合、すなわちある kk が 0≤k≤n0 \le k \le n を満たすとき、その kk 人の男子は (nk)\binom{n}{k} 通りで選べ、残りの n−kn-k 人は女子でなければならず、nn 人の女子から (nn−k)\binom{n}{n-k} 通りで選ばれる。対称性の恒等式 (nn−k)=(nk)\binom{n}{n-k} = \binom{n}{k} より、ちょうど kk 人の男子を含む委員会の数は (nk)⋅(nk)=(nk)2\binom{n}{k} \cdot \binom{n}{k} = \binom{n}{k}^2 である。

nn 人のすべての有効な委員会は 00 から nn の間のある確定した男子の人数 kk を持ち、異なる kk の値で二重に数えられる委員会はないため、すべての kk について和を取ると委員会の総数は ∑k=0n(nk)2\sum_{k=0}^{n} \binom{n}{k}^2 となる。

両方の式が全く同じ委員会の集合を数えているため、それらは等しくなければならない:∑k=0n(nk)2=(2nn)\sum_{k=0}^{n} \binom{n}{k}^2 = \binom{2n}{n}。

大学実世界での応用と具体例

二重数え上げと極値グラフ評価は競技の技だけではない:ネットワーク技術者はケーブルを敷設する前に提案された接続トポロジーの実現可能性を確認するために握手補題型の次数論法を使い、Turán型の三角形なし評価は相互干渉を避ける無線チャネル割り当ての設計に現れる(相互干渉の三角形を作る三つの送信機が同時に稼働することはできない)。以下の二つの具体例は、二重数え上げと極値評価の技法を具体的な競技設定で示す。

例: 握手の偶奇パズル

2525 人の会議で、いくつかの組が握手をする(各組は高々1回)。握手をした回数が奇数である人の数は偶数であることを証明せよ。

解答

人々をグラフ GG の頂点としてモデル化し、二人が握手したときにちょうど辺を引く。すると人 vv の握手回数は deg⁡(v)\deg(v) である。

握手補題により ∑vdeg⁡(v)=2∣E∣\sum_{v} \deg(v) = 2|E| であり、これは握手が何回起きたかにかかわらず偶数である。

和を次数が偶数の人と奇数の人に分ける:∑vdeg⁡(v)=∑deg⁡(v) evendeg⁡(v)+∑deg⁡(v) odddeg⁡(v)\sum_{v} \deg(v) = \sum_{\deg(v)\text{ even}} \deg(v) + \sum_{\deg(v)\text{ odd}} \deg(v)。最初の和は偶数の和なので偶数である。

全体の和が偶数で最初の部分和も偶数であるため、二番目の部分和(奇数次数の和)も偶数でなければならない。しかし奇数の和が偶数になるのは項数が偶数個のときに限るため、奇数次数を持つ人の数——奇数回握手した人の数——は偶数でなければならない。

例: 9局における最大干渉フリーチャネルグラフ

99 局からなる無線ネットワークがあり、二局間のリンクは相互干渉の三角形を作らない場合のみ許される(33 局が互いにリンクすることはない)。可能な最大リンク数はいくつで、どの配置がそれを達成するか?

解答

「相互干渉の三角形がない」という条件は、n=9n=9 局に対するMantelの定理の三角形なし条件そのものであるため、最大リンク数は ⌊92/4⌋=⌊81/4⌋=20\lfloor 9^2/4 \rfloor = \lfloor 81/4 \rfloor = 20 である。

この限界を達成するには、99 局を大きさ 44 と 55 の二グループに分け、異なるグループにある局のすべての対をリンクする(完全二部配置 K4,5K_{4,5})。同じグループ内のリンクは許さない。

この配置には三角形がない。なぜなら三角形には同じグループ内の二局間の辺が必要だが、そのような辺は存在しないからである。リンク数はちょうど 4×5=204 \times 5 = 20 であり、Mantelの定理による限界と一致するため、これは最適である。

Mantelの定理により、1010 頂点の三角形を含まないグラフは最大でいくつの辺を持つか?

1515 人のパーティーで、いくつかの組が握手をする。握手補題により、次のうち握手を奇数回した人の数として起こり得ないものはどれか?

二重数え上げの議論(nn 人の男子と nn 人の女子から nn 人を選ぶ)を用いると、和 ∑k=0n(nk)2\sum_{k=0}^n \binom{n}{k}^2 はどの閉じた形に等しいか?

Combinatorial Nullstellensatzは、組合せ構造の存在を示すことを求める競技問題に対して次を証明することで最も直接的に役立つ:

参考文献

  1. Noga Alon (1999). Combinatorial Nullstellensatz
  2. Béla Bollobás (1998). Modern Graph Theory
  3. Titu Andreescu, Zuming Feng (2003). 102 Combinatorial Problems