JMO2024予選 12
本記事ではJMO2024予選の12番を解説します．
問題
次の条件をみたす$0$以上$2099$以下の整数の組$(a_1,a_2,\dots,a_{2100})$の個数を求めよ．
- 整数の組$(b_1,b_2,\dots,b_{2100})$であって，任意の$1$以上$2100$以下の整数$i$に対して
$$a_i\equiv \sum_{\substack{\mathrm{gcd}(j-i,2100)=1\\1\leqq j\leqq 2100}}b_j\pmod {2100}$$
となるものが存在する．
解答
$\mathrm{gcd}(j-i,2100)=1$は$\mathrm{gcd}(j-i,210)=1$と同値であるため，$a_i=a_{i+210}$が必要である．$x_j=b_j+b_{j+210}+\cdots+b_{j+1890}$とおくと，問題文中の条件は
$$
\quad\sum_{\substack{\mathrm{gcd}(j-i,210)=1\\1\leqq j\leqq 210}}x_j \equiv a_i \pmod{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)$のように書くことにすると，中国剰余定理より上の方程式は
$$
\quad\sum_{\substack{0\leqq p\leqq 1\\p\neq i}}
\sum_{\substack{0\leqq q\leqq 2\\q\neq j}}
\sum_{\substack{0\leqq r\leqq 4\\r\neq k}}
\sum_{\substack{0\leqq s\leqq 6\\s\neq l}}x(p,q,r,s)
\equiv a(i,j,k,l) \pmod{2100}$$
と表せる．この方程式が整数解を持つことは，以下の方程式が整数解を持つことと同値である．
$$\sum_{\substack{0\leqq q\leqq 2\\q\neq j}}
\sum_{\substack{0\leqq r\leqq 4\\r\neq k}}
\sum_{\substack{0\leqq s\leqq 6\\s\neq l}}x(i,q,r,s)
\equiv a(i,j,k,l)\pmod{2100}$$
よって問題は次のように言い換えられる．
次の条件をみたす$0$以上$2099$以下の整数の組$(a_1,a_2,\dots,a_{210})$の個数を求めよ．
- 整数の組$(x_1,x_2,\dots,x_{210})$であって
$$\sum_{\substack{0\leqq q\leqq 2\\q\neq j}} \sum_{\substack{0\leqq r\leqq 4\\r\neq k}} \sum_{\substack{0\leqq s\leqq 6\\s\neq l}}x(i,q,r,s) \equiv a(i,j,k,l)\pmod{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_{\substack{0\leqq q\leqq 2\\q\neq j}}\sum_{0\leqq r\leqq 4}\sum_{0\leqq s\leqq 6}x(i,q,r,s)\pmod{2100}
$$
が成り立つので，$\sum_{k,l}a(i,j,k,l) \equiv 0\pmod{12}$が必要である．同様に以下が必要であることがわかる．
- $\sum_j a(i,j,k,l)\equiv 0\pmod {2}$.
- $\sum_k a(i,j,k,l)\equiv 0\pmod {4}$.
- $\sum_l a(i,j,k,l)\equiv 0\pmod {6}$.
- $\sum_{j,k} a(i,j,k,l)\equiv 0\pmod {4}$.
- $\sum_{j,l} a(i,j,k,l)\equiv 0\pmod {12}$.
- $\sum_{k,l} a(i,j,k,l)\equiv 0\pmod {12}$.
- $\sum_{j,k,l} a(i,j,k,l)\equiv 0\pmod {12}$.
逆にこれらをみたせば十分であることを示そう．
組$(a_1,a_2,\dots,a_{210})$が上の(1)-(7)をみたすと仮定する．まず以下をみたす整数の組$(A_1,\dots,A_{210})$を構成する．
- $\sum_j A(i,j,k,l)\equiv 0\pmod {2}$.
- $\sum_k A(i,j,k,l)\equiv 0\pmod {4}$.
- $\sum_l A(i,j,k,l)\equiv 0\pmod {6}$.
- $\sum_{j,k} A(i,j,k,l)\equiv 0\pmod {8}$.
- $\sum_{j,l} A(i,j,k,l)\equiv 0\pmod {12}$.
- $\sum_{k,l} A(i,j,k,l)\equiv 0\pmod {24}$.
- $\sum_{j,k,l} A(i,j,k,l)\equiv 0\pmod {48}$.
- $A(i,j,k,l)\equiv a(i,j,k,l)\pmod{2100}$.
これは次のような手順で構成できる（$3\times 5\times 7$の直方体を想像するとわかりやすい）．
- $j,k,l$のうち$0$が$1$つ以下であれば$A(i,j,k,l) = a(i,j,k,l)$とする．
- $l\neq 0$に対し，$A(i,0,0,l) = \begin{cases}a(i,0,0,l)\\a(i,0,0,l)+2100\end{cases}$のうち(iv)をみたす方を選ぶ．
- $k\neq 0$に対し，$A(i,0,k,0) = a(i,0,k,0)$とする．
- $j\neq 0$に対し，$A(i,j,0,0) = \begin{cases}a(i,j,0,0)\\a(i,j,0,0)+2100\end{cases}$のうち(vi)をみたす方を選ぶ．
- $A(i,0,0,0) = \begin{cases}a(i,0,0,0)\\a(i,0,0,0)+2100\\a(i,0,0,0)+4200\\a(i,0,0,0)+6300\end{cases}$のうち(vii)をみたすものを選ぶ．
以上で(i)-(viii)をみたす$(A_1,\dots,A_{210})$が構成できた．条件(i)より，連立方程式
$$
\begin{cases}
z(i,1,k,l) + z(i,2,k,l) = A(i,0,k,l)\\
z(i,0,k,l) + z(i,2,k,l) = A(i,1,k,l)\\
z(i,0,k,l) + z(i,1,k,l) = A(i,2,k,l)\\
\end{cases}
$$
を解くと$z(i,j,k,l)$は整数となる．条件(iv),(ii)より$\sum_{k}z(i,j,k,l)\equiv 0\pmod{4}$であるため，連立方程式
\begin{cases}
y(i,j,1,l) + y(i,j,2,l) + y(i,j,3,l) + y(i,j,4,l)= z(i,j,0,l)\\
y(i,j,0,l) + y(i,j,2,l) + y(i,j,3,l) + y(i,j,4,l)= z(i,j,1,l)\\
\vdots\\
y(i,j,0,l) + y(i,j,1,l) + y(i,j,2,l) + y(i,j,3,l)= z(i,j,4,l)
\end{cases}
を解くと$y(i,j,k,l)$は整数となる．条件(vii),(vi)より$\sum_{k,l} z(i,j,k,l)\equiv 0\pmod{24}$であり，条件(v),(iii)より$\sum_l z(i,j,k,l)\equiv 0\pmod{6}$である．これらを合わせると$\sum_{l} y(i,j,k,l)\equiv 0\pmod{6}$が得られるので，連立方程式
\begin{cases}
x(i,j,k,1) + x(i,j,k,2) + \cdots + x(i,j,k,6)= y(i,j,k,0)\\
x(i,j,k,0) + x(i,j,k,2) + \cdots + x(i,j,k,6)= y(i,j,k,1)\\
\vdots\\
x(i,j,k,0) + x(i,j,k,1) + \cdots + x(i,j,k,5)= y(i,j,k,6)\\
\end{cases}
を解くと$x(i,j,k,l)$は整数となる．このとき
$$
\sum_{\substack{0\leqq q\leqq 2\\q\neq j}}
\sum_{\substack{0\leqq r\leqq 4\\r\neq k}}
\sum_{\substack{0\leqq s\leqq 6\\s\neq l}}x(i,q,r,s) = A(i,j,k,l) \equiv a(i,j,k,l)\pmod {2100}
$$
となるのでよい．
以上により，(1)-(7)をみたす$(a_1,\dots,a_{210})$を数える問題に帰着された．このような組は以下の手順で構成できる．
- $j\neq 0,\;k\neq 0,\;l\neq 0$に対する$a(i,j,k,l)$を自由に決める．
- $k\neq 0,\;l\neq 0$に対する$a(i,0,k,l)$を，(1)をみたすように決める．
- $j\neq 0,\;l\neq 0$に対する$a(i,j,0,l)$を，(2)をみたすように決める．
- $j\neq 0,\;k\neq 0$に対する$a(i,j,k,0)$を，(3)をみたすように決める．
- $l\neq 0$に対する$a(i,0,0,l)$を，(4)をみたすように決める．
- $k\neq 0$に対する$a(i,0,k,0)$を，(5)をみたすように決める．
- $j\neq 0$に対する$a(i,j,0,0)$を，(6)をみたすように決める．
- $a(i,0,0,0)$を，(7)をみたすように決める．
各段階での選択肢の個数の総積を求めればよいので，答えは
$$
2100^{96}\cdot \biggl(\dfrac{2100}{2}\biggr)^{48}\cdot \biggl(\dfrac{2100}{4}\biggr)^{24}\cdot \biggl(\dfrac{2100}{6}\biggr)^{16}\cdot \biggl(\dfrac{2100}{4}\biggr)^{12} \cdot \biggl(\dfrac{2100}{12}\biggr)^{8}\cdot \biggl(\dfrac{2100}{12}\biggr)^{4}\cdot \biggl(\dfrac{2100}{12}\biggr)^2=\mathbf{\dfrac{2100^{210}}{2^{164}\cdot 3^{30}}}.
$$
感想
「$2100$と互いに素」という条件が中国剰余定理によって綺麗に言い換えられるのが要点である．(1)-(7)が必要十分であることが予想できればエスパーが可能だが，それを差し引いても12番にふさわしい難問だと感じた．
