問題67：Iran TST 2020

問題一覧へ戻る

#67

組み合わせ

★☆☆☆☆

Iran TST 2020 Test1 問1

完全（無向）グラフの各辺に相異なる正の整数が割り当てられており, 以下の条件をみたす：

ちょうど $3$ 辺からなる任意の閉路について, ある $1$ 辺に割り当てられた数は, 残りの $2$ 辺に割り当てられた $2$ 数の和に等しい.

このとき, 適当に各頂点に実数を割り振ることで, 各辺に割り当てられた数が両端点に割り当てられた $2$ 数の差となるようにできることを示せ.

解いてみた

兒玉：主張は割と自然に見える
平山：帰納法とかどうせ回るやろ、知らんけど
兒玉：とりま一番長い辺を取る
平山：死ぬほど自明に見えてきた…
兒玉：終わりっぽい
平山：最長の固定すれば全部決まるじゃん
宿田：最も hogehoge なものを取る、の典型例か…
兒玉：それ
平山：残りの部分で矛盾しないこともすぐわかるのね

解説・感想

工事中

解答

グラフの頂点数が $n$ であるとする. $n ≦ 3$ のとき主張は明らかであるから, 以下 $n ≧ 4$ とする.

グラフの頂点を $v_{1}, \dots, v_{n}$ とおき, 辺 $v_{i} v_{j}$ に割り当てられた数を $f (v_{i} v_{j})$ で表す. 一般性を失わず, $M = f (v_{1} v_{n})$ が割り当てられた数の中で最大であるとしてよい. このとき $i = 2, \dots, n - 1$ に対し $f (v_{1} v_{i}) + f (v_{i} v_{n}) = M$ である.

以下, $v_{i}$ に $f (v_{1} v_{i})$ を割り当てる（ただし $v_{1}$ には $0$ を割り当てる）ことで条件が成立することを示そう. すなわち, 任意の $2 ≦ i < j ≦ n - 1$ に対し $f (v_{i} v_{j}) = | f (v_{1} v_{i}) - f (v_{1} v_{j}) |$ であることを示せばよい.

ある $i < j$ について $f (v_{i} v_{j}) = f (v_{1} v_{i}) + f (v_{1} v_{j})$ であると仮定して矛盾を導く. このとき, $| f (v_{i} v_{n}) - f (v_{j} v_{n}) | = | f (v_{1} v_{i}) - f (v_{1} v_{j}) | \neq f (v_{1} v_{i}) + f (v_{1} v_{j}) = f (v_{i} v_{j})$ より $f (v_{i} v_{j}) = f (v_{i} v_{n}) + f (v_{j} v_{n})$ であるが, このとき $f (v_{i} v_{j}) = f (v_{i} v_{n}) + f (v_{j} v_{n}) = 2 M - f (v_{1} v_{i}) - f (v_{1} v_{j}) = 2 M - f (v_{i} v_{j})$ より $f (v_{i} v_{j}) = M = f (v_{1} v_{n})$ となり, 各辺に割り当てられた数が相異なる条件に反する.

余談.　各辺に割り当てられた数が相異なるとは限らないとき, 題意は成立しない. 反例を構成してみよ.