NF杯2024(N) - 補題の前までを組み合わせ的に

本解では代数的に記述されている部分が多いので，補題の前までを組み合わせ的に考える方法を与える．

まず，カードに書かれてある数の集合 $\{ 1,2,\dots, 2024\}$を，次の二つに分解する： $$A = \{ 3,4,\dots, 2023,2024\}, \qquad B=\{ 1,2 \}$$ このとき，どの$i=0,1,2,3,4,5$ に対しても，$A$の中には $\bmod{6}$ で $i$であるような要素がちょうど $337$ 個存在することに注意する．

以降，記録された $n$ 個の数字を並べて列 $X=(x_1, \dots, x_n)$ を考え，$x_i\in A$ であるか $x_i\in B$ であるかによって，列$X$ を $(A,A,B,A,\dots, A)$ のような $A,B$ の列に変換した列を $Y$ とよぶ．

　$Y$ の中に $A$ が $k$ 個 ($k =1,2,\dots, 2024$) 含まれている場合に$S_n\equiv i\pmod{6}$ となる場合の数を計算する．そのような $Y$ を一つ取る．たとえば，$Y = (B,B,\dots, B, A, A, \dots, A)$ のような列を考える．このとき， $x_1,\dots, x_{n-1}$ の数字が何であっても，最後の $x_n \in A$ でちょうど $337$ 個の数字が存在して， $S_n \equiv i\pmod{6}$ が成り立つようにできる．よって，このときの場合の数は $2^{n-k}\cdot 2024^{k}\cdot 337 = \frac{1}{6}\cdot 2^{n-k}\cdot 2024^{n}$ なので，その他の $Y$ および $k$ について足し上げることで $$\sum_{k=1}^{n} \frac{{}_{n}\mathrm{C}_k}{6}\cdot 2^{n-k}\cdot 2024^{k}$$ が，「$Y$ の中に $A$ が少なくとも一つ含まれるでかつ $S_n\equiv i\pmod{6}$ となる場合の数」となる．これが $i$ に依存しないことに注意すれば，残りの確率を $Q(n,i)$，すなわち $$P(n,i) = \frac{1}{2024^n}\left( \sum_{k=1}^{n} \frac{{}_{n}\mathrm{C}_k}{6}\cdot 2^{n-k}\cdot 2024^{k} \right) + Q(n,i)$$ と書いたときに， $$\max_{i} P(n,i) - \min_{i} P(n,i) = \max_{i} Q(n,i) - \min_{i} Q(n,i)$$ となる．そして，この $Q(n,i)$ は要するに 「$Y=(B,B,\dots, B,B)$ かつ $S_n\equiv i\pmod{6}$ となる確率」なので，$(x+x^2)^{n}$ の係数について考えることに帰着される．

　この考え方において肝心なのは，$A$ という対称性の高い集合を無理やり作り出す部分であり，これによって 対称性から外れてしまった(しかし要素数が少なくてシンプルな) 集合 $B$ 上の問題へと帰着させることができる（参考：https://mathlog.info/articles/nNX6dXUeyb35vYurGP5l ）．