NMO予選問10個人的解法

https://x.com/nada_mathclub/status/1948380957406302344

$x,y,z$ 空間の格子路の問題に言い換えたい.

• Nドームを $1$ つ追加する操作を $x$ 方向に $1$ 進む操作
• Nドームを $1$ つ破壊する操作を $y$ 方向に $1$ 進む操作
• Nドームを $2$ つ追加する操作を $z$ 方向に $1$ 進む操作
  とそれぞれみなすと, $z=0,x+1 \ge y$ または　$z=1,x+3 \ge y$ を満たす領域内を移動する経路と問の操作に対応が取れます.
  $(0,0,0)$ から $(a,b,c)$ までの領域内の最短経路の個数を $g(a,b,c)$ とすると,
  $$ \begin{aligned}f(1001)&=\sum_{k=0}^{501}g(1000-k,k,1)\\ &=\sum_{k=0}^{501}(g(999-k,k,1)+g(1000-k,k-1,1)+g(k,1000-k,0))\\ &=g(498,501,1)+2\bigg(\sum_{k=0}^{500}g(999-k,k,1)\bigg)+\bigg(\sum_{k=0}^{500}g(1000-k,k,0)\bigg)\\ \end{aligned}$$
  $$f(1000)=\sum_{k=0}^{501}g(999-k,k,1)$$
  よって,
  $$f(1001)-2f(1000)=\bigg(\sum_{k=0}^{500}g(1000-k,k,0)\bigg)-g(498,501,1)$$

$\sum_{k=0}^{500}g(k,1000-k,0)$ を求める.

$(0,0)$ と直線 $y-x=2$ に対して, 対称な点は $(-2,2)$ であり, カタランの鏡像法より, $g(n,m,0)$ は 「$(0,0)$ から $(n,m)$ へ進む経路数」から, 「$(-2,2)$ から $(n,m)$ へ進む経路数」を引いたものであり,
$$ \begin{aligned} &\sum_{k=0}^{500}g(1000-k,k,0)\\ &=\sum_{k=0}^{500}\bigg(\binom{1000-k+k}{1000-k}-\binom{(1000-(k-2))+(k-2))}{1000-(k-2)}\bigg)\\ &=\binom{1000}{500}+\binom{1000}{501}\\ &=\binom{1001}{501} \end{aligned}$$

$g(498,501,1)$ を求める.

$z$ 軸方法にいつ動くのかを考える必要があり, 難しい. ここで, 一旦 $z$ 軸方向の動きを考えることをやめて, $x+3 \ge y$ 内で, $(0,0)$ から $(498,501)$ への移動を考える.
このとき, 経路内で必ず, 直線 $x+2=y$ 上の点に触れる. 最初に触れる$x+2=y$ 上の点
を $(k,k+2)$ とする. このとき, $(0,0)$ から $(k,k+1)$ までの移動経路は, $x+1\ge y$ 内を動くからカタラン数の母関数を
$$c(x)=\sum_{k=0}^{\infty}\frac{1}{k+1}\binom{2k}{k}x^k$$
とすると, $[x^{k}]c(x)^2$ 通りとなる.
そして, $(k,k+2)$ から $(498,501)$ までの経路は,「$(0,0)$ から $(498-k,501-(k+2))$ まで $x+1\ge y$ 内を動く経路数」と等しく, $[x^{498-k}]c(x)^2$ である. ここで, $z$ 軸方向の移動を考える. $z$ 軸方向の移動を挿入しても良い点は, $(0,0)$ から $(k,k+1)$ までの $2k+2$ 個の点である. したがってこれらを考えると,
$$ \begin{aligned} &g(498,501,1)\\ &=\sum_{k=0}^{498}\big([x^{k}]c(x)^2\big)\times (2k+2) \times \big([x^{498-k}]c(x)^2\big)\\ &=2\sum_{k=0}^{498}\big((k+1)[x^{k}]c(x)^2\big) \times \big([x^{498-k}]c(x)^2\big)\\ &=2\sum_{k=0}^{498}\bigg([x^{k}]\frac{d}{dx}\big(xc(x)^2\big)\bigg) \times \big([x^{498-k}]c(x)^2\big)\\ &=2\sum_{k=0}^{498}\bigg([x^{k}]\frac{c(x)^2}{\sqrt{1-4x}}\bigg) \times \big([x^{498-k}]c(x)^2\big)\\ &=2[x^{498}]\frac{c(x)^4}{\sqrt{1-4x}}\\ &=2\binom{2\times498+4}{498}=2\binom{1000}{498} \end{aligned}$$
したがって, 求めるものは,
$$f(1001)-2f(1000)=\bigg(\sum_{k=0}^{500}g(1000-k,k,0)\bigg)-g(498,501,1)=\binom{1001}{501}-2\binom{1000}{498}$$