KMO2025 高等部 1次審査第2問証明

2025年に行われた第39回韓国数学オリンピック高等部1次審査の第2問の証明を書いてみました．

問題

問題．
次の三つの条件をすべて満たす正の整数の順序対$(a_1, a_2, \dots, a_8)$の個数を$1000$で割った余りを求めよ．
(i) 各$i \ (1 \leq i \leq 7)$について，$a_i+a_{i+1}$は偶数である．
(ii) 各$i \ (1 \leq i \leq 6)$について，$a_i+a_{i+1}+a_{i+2}$は$3$の倍数である．
(iii) 各$i \ (1 \leq i \leq 8)$について，$a_i \leq 12$である．

証明

与えられた条件をすべて満たす正の整数の順序対$(a_1, a_2, \dots, a_8)$を，$a_1$の値を仮定して求める．

条件(i)により，$a_1$と$a_2$の偶奇は一致し，かつ条件(iii)より$a_2$の値は$6$通り．

また，条件(i), (ii)より，すべての$i \ (1 \leq i \leq 6)$について以下の2式を満たす．

$$\begin{align}
a_{i+2} &\equiv-a_{i+1} &\pmod 2 \tag{1}\\
a_{i+2} &\equiv-a_i-a_{i+1} &\pmod 3 \tag{2}
\end{align}$$

中国剰余定理より，(1), (2)式を満たす$a_{i+2}$は，$6$を法として一意に定まる．また，$1$から$12$のうち，$6$による剰余が一致する整数は$2$個ずつ存在する．

それゆえ，$a_3, a_4, \dots, a_8$はそれぞれ値が$2$通りに定まる．

以上の議論は$a_1$の値に依らないので，求める正の整数の順序対$(a_1, a_2, \dots, a_8)$の個数は，

$$12 \times 6 \times 2^6 = 4608$$

ゆえに，$608$．

感想

どの問題も解が$1000$以上の場合は$1000$で割った余りを書けと書かれているっぽいです．