MathLabs

第3問

4n4n 個の小石があり、重さはそれぞれ 1,2,3,…,4n1, 2, 3, \ldots, 4n である。各小石は nn 色のいずれか一色で塗られており、各色の小石はちょうど4個ずつある。石を二つの山に分けて、両方の山の総重量が等しく、かつそれぞれの山に各色の石がちょうど2個ずつ含まれるようにできることを示せ。
ステップ 4/6: 各頂点での局所的な釣り合いを確認する
前のステップ次のステップ
ざっくり言うと

厳密な交互性により、頂点を通過するたびに出会う2本の辺は異なる色になることが強制され、次数4の頂点はちょうど2回通過される。

deg⁡blue(v)=deg⁡green(v)=2 for every vertex v.\deg_{\text{blue}}(v)=\deg_{\text{green}}(v)=2\ \text{for every vertex}\ v.
詳しい解説

次数4の頂点はオイラー閉路で2回現れる。通常の通過では、入る辺と出る辺の色が異なるので、その通過は青1つと緑1つの接続を与える。ループを通過する場合、ループは自身の1色で2つの接続を与え、そのループの巡回順で直前と直後の2つの接続は反対の色になる（ループが2つなら、それらの色は交互になる）。したがってどの場合も、頂点の4つの接続を数えると青2つ、緑2つとなる。