和田杯 2024-3 を解いた

下端，上端を$(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.$

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

下端で場合分けを行う．すなわち，$(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} \bigg(\binom{n+1}{2} - \binom{a}{2}-\binom{b}{2} \bigg) \\ &= \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}.$$
以上より示された．

（前半）地面$G=(a,b)$について，$A=ab-1$である．また命題3の証明の前半より$B=\binom{n+1}{2}-\binom{a}{2}-\binom{b}{2}$である．従って示すべきことは，
$$\begin{aligned} A\leq B &\iff 2ab-2 \leq n(n+1)-a(a+1)-b(b-1) \\ &\iff (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 &\iff 2(e+1)(f+1)-2 \leq n(n-1)-e(e-1)-f(f-1)\\ &\iff (e+f+1)(e+f) \leq n(n-1). \end{aligned}$$
いま$e+f=2n-(c+d)\leq n-1$だから，示された．