| For All Solvers
NF杯2024

NF杯2024(M) - 漸化式と帰納法による解法

ユーザー解説 by igma

　n×nn\times n のマス目に対して輝く書き込みおよび輝度を同様に定め，すべての輝く書き込みの輝度を足し合わせた値を ana_n とおく．また，a0=1a_0=1 とする．

　n≥3n\geq 3 とし，ana_n を an−1,…,a1,a0a_{n-1},\dots ,a_1,a_0 を用いて表す．まず 11 が 11 行 11 列目に書き込まれているとき，残りの数字の書き込み方は (n−1)×(n−1)(n-1)\times (n-1) のマス目の輝く書き込み方と等しい．よってこの場合の輝度の和は 2an−1.2a_{n-1}.

　11 が 11 行 ii 列目 (2≤i≤n)(2\leq i\leq n) に書き込まれているとき，ii は ii 列目に書き込むことが出来ないので，ii の書き込み方は (n−1)(n-1) 通りある．そのうち ii を ii 行 11 列目に書き込む場合，残りの数字の書き込み方は (n−2)×(n−2)(n-2)\times (n-2) のマス目の輝く書き込み方に等しいので，この場合の輝度の和は an−2a_{n-2}．残りの (n−2)(n-2) 通りの場合，すなわち ii を ii 行 jj 列目 (j≠1,i)(j\neq 1,i) に書き込む場合，jj の書き込み方は (n−2)(n-2) 通りだが，そのうち jj を 11 列目に書き込む場合の輝度の和は上と同様に考えて an−3a_{n-3}．以下同様に考えていくと，11 が 11 行 ii 列目 (2≤i≤n)(2\leq i\leq n) に書き込まれる場合の輝度の和は

∑k=0n−2n−2Pkan−k−2\sum_{k=0}^{n-2}{}_{n-2}\mathrm{P}_{k}a_{n-k-2}

である．これが任意の i=2,…,ni=2,\dots ,n で成り立ち，かつ 11 が ii 行 11 列目 (i≠1)(i\neq 1) に書き込まれる場合も同様であるので，全ての場合を足し合わせて

an=2∑k=0n−1n−1Pkan−k−1=2∑k=0n−1(n−1)!(n−k−1)!an−k−1a_n=2\sum_{k=0}^{n-1}{}_{n-1}\mathrm{P}_{k}a_{n-k-1}=2\sum_{k=0}^{n-1}\frac{(n-1)!}{(n-k-1)!}a_{n-k-1}

と表せる．ここで，ak=(k+1)!a_k=(k+1)! (k=1,…,n−1)(k=1,\dots, n-1) と仮定すると

2∑k=0n−1(n−1)!(n−k−1)!an−k−1=2∑k=0n−1(n−1)!(n−k−1)!(n−k)!=2∑k=0n−1(n−k)(n−1)!=2⋅n(n+1)2(n−1)!=(n+1)!\begin{aligned} 2\sum_{k=0}^{n-1}\frac{(n-1)!}{(n-k-1)!}a_{n-k-1}&=2\sum_{k=0}^{n-1}\frac{(n-1)!}{(n-k-1)!}(n-k)!\\ &=2\sum_{k=0}^{n-1}(n-k)(n-1)!\\ &=2\cdot \frac{n(n+1)}{2}(n-1)!\\ &=(n+1)! \end{aligned}

となるので，a1=2!,a2=3!a_1=2!, a_2=3! より帰納法が成立し，任意の正整数 nn に対して an=(n+1)!a_n=(n+1)! となる．特に a999=1000!a_{999}=1000! であり，ルジャンドルの定理より求める答えは 249\mathbf{249} である．