和田杯 2024-3 を解いた

291

お久しぶりです．題名の通りです．

まずは問題を述べます. $n$ は固定された $2$ 以上の正整数値であるとして良いと思います．

2024 年度和田杯 3

$x y$ 平面上に置いてある点が良い点であるとは，その点の $x$ 座標と $y$ 座標が共に $1$ 以上 $n$ 以下の正整数であることを指すものとする． $N$ 匹のウサギが $(1, 1)$ から $(n, n)$ まで，良い点から良い点への移動のみで移動する．また，ウサギは今いる良い点より $x$ 座標と $y$ 座標の少なくとも一方が小さい点には移動できないものとする．このとき，任意の $1 \leq i \leq j \leq n, 1 \leq k \leq l \leq n, (i, j) \neq (k, l)$ を満たす整数 $i, j, k, l$ に対して， $(i, k)$ から $(j, l)$ へ移動したウサギが存在したという．ウサギの匹数としてありえる最小値を求めよ．

解答

まず言葉の定義をする．

良い点 $(a, b)$ から $(c, d)$ への移動であって， $a \leq c, b \leq d, (a, b) \neq (c, d)$ を満たすものをジャンプと呼ぶ．またこのとき $(a, b)$ をこのジャンプの下端， $(c, d)$ をこのジャンプの上端と呼ぶ．
良い点 $(a, b)$ に対し，そのスコアを $a + b$ で定義する．

ウサギの移動の制約はジャンプのみで移動すること，問題は「できるだけ少ない数のウサギで，あり得るジャンプをすべて含むようにせよ」と言い換えられる．

あるジャンプの上端のスコアは，下端のスコアより大きい．

下端，上端を $(a, b), (c, d)$ とする． $a \leq c, b \leq d$ より $a + b \leq c + d .$
$a + b = c + d$ とすると $(a, b) = (c, d)$ であるから矛盾． $a + b < c + d .$

ジャンプであって，下端のスコアが $n$ 以下であり，かつ上端のスコアが $n + 1$ 以上であるものを大ジャンプと呼ぶ．大ジャンプ全体の集合を $J_{B}$ とおく．

ウサギは， $2$ つ以上の大ジャンプをしない．

あるウサギが $2$ つの大ジャンプ $J_{1}, J_{2}$ をするとする．ここで $J_{1}$ よりも後に $J_{2}$ を行うものとする．命題1より， $J_{1}$ の上端のスコアは， $J_{2}$ の下端のスコア以下であるが，これは大ジャンプの定義に矛盾する．よって示された．

命題2と問題の条件より， $N \geq # J_{B}$ である． $# J_{B}$ について次を示す．

$# J_{B} = (\binom{n + 1}{2}) (\binom{n}{2}) - 2 (\binom{n + 1}{4}) .$
ここで $(\binom{a}{b})$ は二項係数．

下端で場合分けを行う．すなわち， $(a, b)$ がスコアが $n$ 以下であるような点であるとして，これを下端とする大ジャンプの個数を調べる．
これは良い点 $(c, d)$ であって，スコアが $n + 1$ 以上かつ $c \geq a, d \geq b$ を満たすものの個数に等しい．スコアが $n + 1$ 以上の良い点は $(\binom{n + 1}{2})$ 個であるから，ここから

スコアが $n + 1$ 以上であり，
$c < a$ または $d < b$ である

ようなものの個数を引けばよい．一つ目の条件の下で，二つ目の条件が両方満たされることはなく，二つ目の前者の条件を満たすようなものは $(\binom{a}{2})$ 個，後者の条件を満たすようなものは $(\binom{b}{2})$ 個存在するから，これは $(\binom{a}{2}) + (\binom{b}{2})$ 個である．従って次のように計算できる．
$\begin{aligned} # J_{B} & = \sum_{a + b \leq n} ((\binom{n + 1}{2}) - (\binom{a}{2}) - (\binom{b}{2})) \\ = (\binom{n + 1}{2}) (\binom{n}{2}) - \sum_{a + b \leq n} (\binom{a}{2}) - \sum_{a + b \leq n} (\binom{b}{2}) \\ = (\binom{n + 1}{2}) (\binom{n}{2}) - \sum_{a = 1}^{n - 1} \sum_{b = 1}^{n - a} (\binom{a}{2}) - \sum_{b = 1}^{n - 1} \sum_{a = 1}^{n - b} (\binom{b}{2}) \\ = (\binom{n + 1}{2}) (\binom{n}{2}) - 2 \sum_{a = 1}^{n - 1} (n - a) (\binom{a}{2}) \\ = (\binom{n + 1}{2}) (\binom{n}{2}) - 2 (\binom{n + 1}{4}) \end{aligned}$
ここで最後の等号には次の事実を $i = 2, j = 1$ として用いた（※）：
$\sum_{a + b = n} (\binom{a}{i}) (\binom{b}{j}) = (\binom{n + 1}{i + j + 1}) .$
以上より示された．

逆に $N = # J_{B}$ であるようなウサギの移動があることを示す．
改めて，スコアが $n$ 以下である良い点を地面，そうでない良い点を空と呼ぶ．
$J_{B}$ に含まれないジャンプは，下端と上端がともに地面か，ともに空であるものである．

任意の地面 $G$ について，以下のように定めると $A \leq B$ である．

上端を $G$ とするジャンプの個数を $A$ とする．
下端を $G$ とする大ジャンプの個数を $B$ とする．

また，任意の空 $S$ について，以下のように定めると $C \leq D$ である．

下端を $S$ とするジャンプの個数を $C$ とする．
上端を $S$ とする大ジャンプの個数を $D$ とする．

（前半）地面 $G = (a, b)$ について， $A = a b - 1$ である．また命題3の証明の前半より $B = (\binom{n + 1}{2}) - (\binom{a}{2}) - (\binom{b}{2})$ である．従って示すべきことは，
$\begin{aligned} A \leq B & ⟺ 2 a b - 2 \leq n (n + 1) - a (a + 1) - b (b - 1) \\ ⟺ (a + b + 1) (a + b - 2) \leq n (n + 1) . \end{aligned}$

これは $a + b \leq n$ より従うから，示された．

（後半）空 $S = (c, d)$ について， $C = (n + 1 - c) (n + 1 - d) - 1$ である．また命題3の証明の前半と同様に， $D = (\binom{n}{2}) - (\binom{n - c}{2}) - (\binom{n - d}{2})$ がわかる．従って,
$e = n - c, f = n - d$ とおくと，示すべきことは
$\begin{aligned} C \leq D & ⟺ 2 (e + 1) (f + 1) - 2 \leq n (n - 1) - e (e - 1) - f (f - 1) \\ ⟺ (e + f + 1) (e + f) \leq n (n - 1) . \end{aligned}$
いま $e + f = 2 n - (c + d) \leq n - 1$ だから，示された．

以下で用いる記号 $A, B, C, D$ は命題4で用いたものと同じものである（これらは地面 $G$ や空 $S$ に応じて決まる値である）．
$# J_{B}$ 匹のウサギに，それぞれ $J_{B}$ の相異なる元を対応付け，次の操作を行う．

各地面 $G$ について， $G$ を下端とする大ジャンプを対応付けられたウサギは $B$ 匹いるから，命題4よりこれらから $A$ 匹を選ぶことができる．一方 $G$ を上端とするジャンプは $A$ 個存在するから，これらを上の $A$ 匹に（適当な順番で）対応付ける．
各空 $S$ について， $S$ を上端とする大ジャンプを対応付けられたウサギは $D$ 匹いるから，命題4よりこれらから $C$ 匹を選ぶことができる．一方 $S$ を下端とするジャンプは $C$ 個存在するから，これらを上の $C$ 匹に（適当な順番で）対応付ける．