OMC034-B後日談

174

皆さんこんにちはこんばんはおじゃめしです！実は, OMC034のABのwriterを担当させていただきました. 今回は特にOMC034-Bついて, 後日談としていろいろ書いていこうと思います. 最後まで読んでくだされば嬉しいです.

今回の問題

今回の問題は以下のようなものでした.

問題(OMC034-B)

$47 行 \times 2021$ 列のマス目があり, この最上行の $2021$ マスには同一のコマがそれぞれ一つずつ置かれています. これらのコマに対し, 以下の操作を $46$ 回にわたって行います. 具体的には, $n$ 回目の操作は以下で定義されます：

・上から数えて $n$ 行目に置かれているコマから一つ以上を選び, 隣接した真下のマスに移動させる.

$46$ 回の操作の後, 最下行に $k$ 個のコマがあるような配置としてありえるものの総数を $S_{k}$ とおきます.
$S_{1}, S_{2}, . . ., S_{2021}$ における最大値を $S$ とするとき, $S$ が $2$ で割り切れる最大の数を求めてください.

（一応, 問題のリンクを貼っておきますこちらです↓）
https://onlinemathcontest.com/contests/omc034/tasks/261

（一応, 解説のリンクも貼っておきますこちらです↓）
https://onlinemathcontest.com/contests/omc034/editorial/261

恐らく, 公式サイトに掲載されているような考え方で $S_{k}$ を求めて計算した方が大半だと思います. ですが実はこれ, 頑張って計算することによっても $S_{k}$ を求めることができます！

以下では, 別解としてその方法を説明していこうと思います.

別解の紹介

まずはじめに, 次の補題を証明しておきます.

非負整数 $m, n (m \geq n)$ と実数 $x$ に対し,以下の等式が成立する.

$\sum_{l = n}^{m}_{m} C_{l} \cdot_{l} C_{n} \cdot x^{l - n} =_{m} C_{n} \cdot (x + 1)^{m - n}$

適当な非負整数 $n, h, i$ を用いて, $m = n + h, l = n + i$ と表すことにすると， $\begin{array}{rcl} \sum_{l = n}^{m}_{m} C_{l} \cdot_{l} C_{n} x^{l - n} & = & \sum_{i = 0}^{h}_{n + h} C_{n + i} \cdot_{n + i} C_{n} x^{i} \\ = & \sum_{i = 0}^{h} \frac{(n + h)!}{(n + i)! (h - i)!} \cdot \frac{(n + i)!}{n! i!} \cdot \frac{h!}{h!} x^{i} \\ = & \sum_{i = 0}^{h}_{n + h} C_{h} \cdot_{h} C_{i} x^{i} \\ = & _{n + h} C_{h} \sum_{i = 0}^{h}_{h} C_{i} x^{i} \\ = & _{m} C_{n} (x + 1)^{m - n} \end{array}$

ちなみに, 他の証明として, お馴染みの式である $\sum_{k = 0}^{m}_{m} C_{k} x^{k} = (1 + x)^{m}$ を $n$ 回微分して整理するという方法もあります.（これに関しては自力では思いつかなかった...）

ここからが本題です. 最上行を第1行とよぶことにし, 第 $n$ 行に移動させたコマの個数を $a_{n}$ とします（なお, 一番はじめのコマの個数を $a_{1}$ とします）. 以下のことを証明していきます.

$j$ 行× $a_{1}$ 列のマス目で問題と同様の操作をおこない, 最下行にちょうど $k$ 個のコマが配置されるようにする. 操作終了後のコマの配置としてありえるものの数を $S_{j, k}$ とおくと，

$S_{j, k} =_{a_{1}} C_{k} \cdot (j - 1)^{a_{1} - k}$

である.

ただし, $j, k$ は整数で $j \geq 2, a_{1} \geq k \geq 1.$ である.

行の本数 $j$ に関する数学的帰納法で示す.

(ア) $j = 2$ のとき

第1行にある $a_{1}$ 個のコマから $k$ 個のコマを選んで隣接する真下のマスに移動させるので,

$S_{2, k} =_{a_{1}} C_{k} =_{a_{1}} C_{k} \cdot (2 - 1)^{a_{1} - k}$

である. よって, $j = 2$ のとき, これは成立している.

(イ) ある $j$ 行の場合において, 上式の成立を仮定する. $j + 1$ 行のときを考える.

第 $j$ 行目に $a_{j}$ 個のコマが存在するように操作を繰り返し, さらに $a_{j}$ 個のコマから $k$ 個のコマを選ぶ. その時のコマの選び方の総数は

$S_{j, a_{j}} \cdot_{a_{j}} C_{k}$

と表せる. $a_{1} \geq a_{j} \geq k$ であるから, この範囲で総和をとれば, $S_{j + 1, k}$ を求めることができる.

$\begin{array}{rcl} S_{j + 1, k} & = & \sum_{a_{j} = k}^{a_{1}} S_{j, a_{j}} \cdot_{a_{j}} C_{k} \\ = & \sum_{a_{j} = k}^{a_{1}}_{a_{1}} C_{a_{j}} (j - 1)^{a_{1} - a_{j}} \cdot_{a_{j}} C_{k} (∵ 帰納法の仮定) \\ = & {(\frac{1}{j - 1})}^{k - a_{1}} \sum_{a_{j} = k}^{a_{1}}_{a_{1}} C_{a_{j}} \cdot_{a_{j}} C_{k} {(\frac{1}{j - 1})}^{a_{j} - k} \\ = & {(\frac{1}{j - 1})}^{k - a_{1}}_{a_{1}} C_{k} \cdot {(\frac{1}{j - 1} + 1)}^{a_{1} - k} (∵ 補題 1) \\ = & _{a_{1}} C_{k} \cdot j^{a_{1} - k} \end{array}$
となる. よって, $j + 1$ 行のときも成立していることがわかる.

(ア)(イ)より, これは示された.

特に今回の問題の場合, $j = 47, a_{1} = 2021$ であるから, $S_{k} = S_{47, k} =_{2021} C_{k} \cdot 46^{2021 - k}$ となります.

以上, かなりゴリ押し気味ですが $S_{k}$ を直接求めることができました！

後日談

最後まで読んでくださってありがとうございました. 今回の問題は, 「ある参考書で補題1の変形を知る（と同時にこの式をいじりたくなってくる） → 変数を増やしてみたら $S_{j, k}$ にたどり着く → $S_{j, k}$ が出てくるようにゲームを設定する」という感じで作った問題でした. 公式解答のように全操作後の盤面の状態を考えればサクッと解ける問題ですが（なお計算量は度外視）, 愚直に考えてもいろいろと深堀りできることがある問題だったように思えます.

最後になりますが, いくつか謝辞（大袈裟？）を.
　OMCの運営の皆様. いつもコンテストの運営お疲れ様です. 今回, writerとしてコンテストに携われたことを嬉しく思います！今後も弥栄の発展を楽しみにしております.
　そして, OMC034に参加してくださったsolverの皆様. 解いてくださりありがとうございます！また, コンテスト後に感想やご意見を残してくださりありがとうございました. 想定より多くのコメントが頂戴できてうれしかったです. これからも, いい感じの問題が作れるように頑張ります！（もちろんsolverとしても精進します...）

ではまた！