問題65：Mexico MO 2019

#65

組み合わせ

★★☆☆☆

Mexico MO 2019 問3

$n ≧ 2$ を整数とする. 円周上に $2 n$ 個の点が打たれており, 各点には $1$ から $n$ までの整数が割り当てられている. ここで, 各整数はちょうど $2$ 点に割り当てられている. チノはこれらの点を $2$ 点からなるペア $n$ 個に分割し, それぞれの間に弦を張り, 各弦に両端点に割り当てられた整数のうち小さくない方を割り当てる. ここで, 弦どうしは交わらないようにする.

　 $(1)$ 点への整数の割り当て方によらず, チノは弦に割り当てられる整数をちょうど $⌈ n / 2 ⌉$ 種類にできることを示せ.

　 $(2)$ チノの行動によらず, 彼女が弦に割り当てる整数が常に $⌈ n / 2 ⌉$ 種類となるような, 点への整数の割り当て方は存在するか？

ここで, 実数 $x$ に対し $⌈ x ⌉$ で $x$ 以上の最小の整数を表す.

解いてみた

馬杉： $n = 2$ は自明
渡辺：帰納法ワンちゃん回せそう？
平山：厳しくない？
馬杉： $(1)$ 方針立ったかも
馬杉：上位と下位にわけて、すべての辺がそれらを繋ぐようにする
馬杉：隣接してる部分から辺で繋げば終わり
宿田：奇数なら $1$ 同士で調整かと思ったけど嘘だ…
馬杉：いずれ真ん中くらいで割ればいい、 $112$ と $233$ みたいな
平山： $(2)$ は反例作りに行く方が簡単か？
馬杉： $n = 2$ は $1212$ で良くて
平山： $3$ も大丈夫、 $1$ 同士を阻止すれば良い、間が奇数個の組は繋げない
馬杉：いま答え言った？？
宿田：だいぶ本質で草
平山：ほんまか？
馬杉：二部グラフっぽい
馬杉：行けた、偶数番目に上位置けばいい
平山：本質でした。

解説・感想

ぽっぴんジャンプ♪ (宿田)

解答

$(1)$ まず次の補題を示す.

補題.

$n \in Z^{+}$ として, 円周上の異なる $2 n$ 点が $2$ つの $n$ 個の点のグループに分けられるとき, $2 n$ 点を $n$ 組のペアに分割してペアどうしを弦で結ぶ方法であって, すべてのペアが異なるグループの $2$ 点を含み, かつ $n$ 個の弦が互いに交わらないものが存在する.

証明.

数学的帰納法で示す. $n = 1$ のときは自明に成り立つ. $n = k$ のときに補題が成り立つとして $n = k + 1$ のときを考える. ある隣りあう二点 $X, Y$ であって異なるグループに属するものが存在する. $X$ と $Y$ をペアにし, 残りの $2 k$ 点を補題の条件をみたすようにペアにすれば, これらのペアは条件をみたす. よって $n = k + 1$ でも補題が成立する.

$2 n$ 個の点を $2$ つの $n$ 個の点のグループに分けて, 一方のグループの点には $⌈ n / 2 ⌉$ 以下の整数が, もう一方のグループの点には $(n + 1 - ⌈ n / 2 ⌉)$ 以上の整数が割り当てられているようにする. 補題より, すべてのペアが異なるグループの $2$ 点を含むように分割する方法が存在し, このとき弦に割り当てられる整数は $(n + 1 - ⌈ n / 2 ⌉)$ 以上 $n$ 以下の整数の $⌈ n / 2 ⌉$ 種類ある.

$(2)$ 存在する. 円周上の点を順番に $A_{1}, A_{2}, \dots, A_{2 n}$ とする. $A_{1}, A_{3}, \dots, A_{2 n - 1}$ に $⌈ n / 2 ⌉$ 以下の整数を, $A_{2}, A_{4}, \dots, A_{2 n}$ に $(n + 1 - ⌈ n / 2 ⌉)$ 以上の整数を割り当てる. さて, 偶奇が等しい整数 $i, j$ について $A_{i}$ と $A_{j}$ がペアになっているとする. このとき, 円周は $A_{i}$ と $A_{j}$ によって $2$ つの弧( $A_{i}$ と $A_{j}$ を含まない)に分けられ, それぞれの弧には奇数個の点が含まれる. よって, あるペアになる $2$ 点であって, それぞれ異なる弧上にあるものが存在するが, これらを結んだ弦は $A_{i} A_{j}$ と交わり不適. したがって, チノは $⌈ n / 2 ⌉$ 以下の整数が割り当てられた点と $(n + 1 - ⌈ n / 2 ⌉)$ 以上の整数が割り当てられた点をペアにする必要があり, 弦に割り当てられる整数は $(n + 1 - ⌈ n / 2 ⌉)$ 以上 $n$ 以下の整数の $⌈ n / 2 ⌉$ 種類である.