NF杯2024(M)

　$S=\{1,\ldots,999\}$ とおく．輝く書き込み $K$ に対し，$i\in S$ であって $i$ 行 $i$ 列目に書き込まれているものを $K$ の輝く数とよび，$i\in S$ のうち $K$ の輝く数でないものを $K$ の輝かない数とよぶ．

　$S$ の部分集合 $A$ に対して，輝く書き込みのうち，以下の $2$ 条件を満たすものの集合を $E(A)$ とする．

• $i\in A$ ならば，$i$ は $i$ 行目のマスに書き込まれている
• $i\not\in A$ ならば，$i$ は $i$ 列目のマスに書き込まれている

　ある輝く書き込み $K$ の輝く数全体を $i_1,\ldots,i_n \in S$ とする．この $K$ に対し， $K\in E(A)$ となるような $A$ の個数は，各 $i_1,\ldots,i_n$ を $A$ に入れるか入れないかを考えることで $2^n$ 通り存在する（$K$ の輝かない数については，$A$ に入るかどうかは一意的に定まる）． すなわち，それぞれの輝く書き込み $K$ に対し，$K\in E(A)$ となるような $A$ の個数は $K$ の輝度と等しいので，輝度の総和は，すべての $A\subset S$ に対する $E(A)$ の要素の個数の総和に等しい．

　$k\in S$ とし，$|A|=k$ となるような $A\subset S$ に対する $|E(A)|$ を求める． $|E(A)|$ は $|A|$ にのみ依存するので，$A={1,\ldots,k}$ としてよい．$K\in E(A)$ となる書き込み $K$ において，$1\leq i\leq k$ が $i$ 行 $j$ 列目（$k+1\leq j\leq 999$）に書かれていると仮定すると，$j\not\in A$ より $j$ は $j$ 列目に書かれているはずだが，これは同じ列に $2$ つ以上の文字が書き込まれないことに反する．よって，$1\leq i\leq k$ なる $i$ が書き込まれうるのは $1$ 列目から $k$ 列目までであり，列の重複を考慮すると，$1$ 列目から $k$ 列目までの書き込み方は $k!$ 通りある．同様に，$k+1$ 列目から $999$ 列目までの書き込み方は $(999-k)!$ 通りあるので，$K\in E(A)$ となる書き込みの個数は $k!(999-k)!$ 通りである．$|A|=k$ となる $A\subset S$ の個数は ${}_{999}\mathrm{C}_k$通りであるから，求める総和は，

$$\sum_{k=0}^{999}{}_{999}\mathrm{C}{}_k \cdot k!(999-k!)=\sum_{k=0}^{999}999!=1000!$$ 　よって，ルジャンドルの定理より，特に解答すべき値は $\mathbf{249}$ である．