JMO2024予選 12

本記事ではJMO2024予選の12番を解説します．

問題

解答

$\gcd (j-i,2100)=1$は$\gcd (j-i,210)=1$と同値であるため，$a_i=a_{i+210}$が必要である．$x_j=b_j+b_{j+210}+\cdots +b_{j+1890}$とおくと，問題文中の条件は
$$\sum _{\begin{array}{c}\gcd (j-i,210)=1\\ 1\leqq j\leqq 210\end{array}}{x}_j\equiv a_i(\mathrm{mod}2100)$$
となるので，これが$x_1,\dots ,x_{210}$に関する方程式として整数解を持つような$(a_1,\dots ,a_{210})$の個数を求めればよい．$n$を$2,3,5,7$で割った余りがそれぞれ$i,j,k,l$であるとき$a_n=a(i,j,k,l)$のように書くことにすると，中国剰余定理より上の方程式は
$$\sum _{\begin{array}{c}0\leqq p\leqq 1\\ p\ne i\end{array}}\sum _{\begin{array}{c}0\leqq q\leqq 2\\ q\ne j\end{array}}\sum _{\begin{array}{c}0\leqq r\leqq 4\\ r\ne k\end{array}}\sum _{\begin{array}{c}0\leqq s\leqq 6\\ s\ne l\end{array}}x(p,q,r,s)\equiv a(i,j,k,l)(\mathrm{mod}2100)$$
と表せる．この方程式が整数解を持つことは，以下の方程式が整数解を持つことと同値である．
$$\sum _{\begin{array}{c}0\leqq q\leqq 2\\ q\ne j\end{array}}\sum _{\begin{array}{c}0\leqq r\leqq 4\\ r\ne k\end{array}}\sum _{\begin{array}{c}0\leqq s\leqq 6\\ s\ne l\end{array}}x(i,q,r,s)\equiv a(i,j,k,l)(\mathrm{mod}2100)$$
よって問題は次のように言い換えられる．

$\sum _{k,l}a(i,j,k,l)=\sum _{k=0}^4\sum _{l=0}^{6}a(i,j,k,l)$のように略記すると，条件をみたす組$(a_1,\dots ,a_{210})$に対しては
$$\sum _{k,l}a(i,j,k,l)\equiv 24\sum _{\begin{array}{c}0\leqq q\leqq 2\\ q\ne j\end{array}}\sum _{0\leqq r\leqq 4}\sum _{0\leqq s\leqq 6}x(i,q,r,s)(\mathrm{mod}2100)$$
が成り立つので，$\sum _{k,l}a(i,j,k,l)\equiv 0(\mathrm{mod}12)$が必要である．同様に以下が必要であることがわかる．

1. $\sum _{j}a(i,j,k,l)\equiv 0(\mathrm{mod}2)$.
2. $\sum _{k}a(i,j,k,l)\equiv 0(\mathrm{mod}4)$.
3. $\sum _{l}a(i,j,k,l)\equiv 0(\mathrm{mod}6)$.
4. $\sum _{j,k}a(i,j,k,l)\equiv 0(\mathrm{mod}4)$.
5. $\sum _{j,l}a(i,j,k,l)\equiv 0(\mathrm{mod}12)$.
6. $\sum _{k,l}a(i,j,k,l)\equiv 0(\mathrm{mod}12)$.
7. $\sum _{j,k,l}a(i,j,k,l)\equiv 0(\mathrm{mod}12)$.

逆にこれらをみたせば十分であることを示そう．

以上により，(1)-(7)をみたす$(a_1,\dots ,a_{210})$を数える問題に帰着された．このような組は以下の手順で構成できる．

• $j\ne 0,k\ne 0,l\ne 0$に対する$a(i,j,k,l)$を自由に決める．
• $k\ne 0,l\ne 0$に対する$a(i,0,k,l)$を，(1)をみたすように決める．
• $j\ne 0,l\ne 0$に対する$a(i,j,0,l)$を，(2)をみたすように決める．
• $j\ne 0,k\ne 0$に対する$a(i,j,k,0)$を，(3)をみたすように決める．
• $l\ne 0$に対する$a(i,0,0,l)$を，(4)をみたすように決める．
• $k\ne 0$に対する$a(i,0,k,0)$を，(5)をみたすように決める．
• $j\ne 0$に対する$a(i,j,0,0)$を，(6)をみたすように決める．
• $a(i,0,0,0)$を，(7)をみたすように決める．

各段階での選択肢の個数の総積を求めればよいので，答えは
$${2100}^{96}\cdot ({\displaystyle \frac{2100}{2}}{)}^{48}\cdot ({\displaystyle \frac{2100}{4}}{)}^{24}\cdot ({\displaystyle \frac{2100}{6}}{)}^{16}\cdot ({\displaystyle \frac{2100}{4}}{)}^{12}\cdot ({\displaystyle \frac{2100}{12}}{)}^8\cdot ({\displaystyle \frac{2100}{12}}{)}^4\cdot ({\displaystyle \frac{2100}{12}}{)}^2={\displaystyle \frac{{\mathbf{2100}}^{\mathbf{210}}}{{\mathbf{2}}^{\mathbf{164}}\cdot {\mathbf{3}}^{\mathbf{30}}}}.$$

感想

「$2100$と互いに素」という条件が中国剰余定理によって綺麗に言い換えられるのが要点である．(1)-(7)が必要十分であることが予想できればエスパーが可能だが，それを差し引いても12番にふさわしい難問だと感じた．