NF杯2024(Q)

　$S$ を問題の総和とする．また，以下では合同式の法は $3$ であるとし，$x_{10+k}=x_{k}, y_{10+k}=y_{k}$ となるように $x_{11}, y_{11}, x_{12}, y_{12}, \dots$ を定める．

　$A= \{ (1,3), (3,1), (1,1), (3,3), (2,2) \}$，$B = \{ (2,1), (1,2), (2,3), (3,2) \}$ とおく．$(a,b) \in A$ であるとき，$a^y + y^b \bmod{3}$ を $y=4,5,6$ に対して計算すると，順に

• $1^y + y^3 \equiv 2,0,1$
• $3^y + y^1 \equiv 1,2,0$
• $1^y + y^1 \equiv 2,0,1$
• $3^y + y^3 \equiv 1,2,0$
• $2^y + y^2 \equiv 2,0,1$

なので，いずれの場合も $0,1,2$ がちょうど $1$ 回ずつ現れることがわかる．

Case 1. $X = (x_1,\dots, x_{10})$ について「$(x_1, x_2), (x_2, x_3), \dots (x_{9}, x_{10}), (x_{10}, x_{1})$ の中に $A$ の要素が少なくとも一つ含まれている」ことを仮定する．その $A$ の要素の一つを $(x_{i}, x_{i+1})$ とおく．このとき $S$ の中の $x_i^{y_i} + y_{i}^{x_{i+1}}$ を見ることで，$y_{i}$ を除く $y_1,y_2,y_3,\dots, y_{10}$ の値を $3^{9}$ 通りの中からどのように決めたとしても，ちょうど一つの $y_{i} \in \{ 4,5,6\}$ が存在して $S\equiv 0$ にすることができる．
　したがって，この仮定を満たす $(x_1,x_2,\dots, x_{10})$ が $N$ 個あるとするとき，条件を満たす列の組 $(X,Y)$ が $3^9\cdot N$ 個得られる．

Case 2. $X = (x_1,\dots, x_{10})$ について，$(x_1, x_2), (x_2,x_3), \dots (x_{9}, x_{10}), (x_{10}, x_{1})\in B$ である場合を考える．このような $X$ は，$k_{i} \in \{ 1,3\}$ を用いて $$(2,k_2,2,k_4,2,k_6,2,k_8,2,k_{10}),\quad (k_1,2,k_3,2,k_5,2,k_7,2,k_9,2)$$ と表せるような $64$ 組のいずれかであることが分かるから，$3^{10} - N = 64$ である．よって $N = 3^{10} - 64$ である．

　$X = (k_1,2,k_3,2,k_5,2,k_7,2,k_9,2)$ の場合を考える．$k_{1}, k_3, k_5, k_7, k_9\in \{ 1, 3\}$ なので $$\begin{aligned} y_{2i-1}^{k_{2i-1}} + k_{2i-1}^{y_{2i}} + y_{2i}^{2} + 2^{y_{2i+1}} \equiv y_{2i-1} + k_{2i-1} + y_{2i}^2 + 2^{y_{2i+1}} \end{aligned}$$ が $i=1,2,3,4,5$ で成り立つ．したがって， $$\begin{aligned} S &\equiv \sum_{i=1}^{5}(2^{y_{2i-1}} + y_{2i-1}) + \sum_{i=1}^{5} y_{2i}^2 + \sum_{i=1}^{5} k_{2i-1} \\ \end{aligned}$$ となる．この式から $S\equiv 0$ となるための $y_1,\dots, y_{10}, k_{1}, k_{3}, \dots, k_{10}$ の条件を考える．

　$y=4,5,6$ のとき $2^y + y \equiv 2,1,1$ および $x^2 \equiv 1,1,0$ である．したがって，$S\equiv 0$ となる $(y_1,y_2,\dots, y_{10}, k_{1}, \dots, k_{5})$ の個数を求めることは，次の場合の数を求めることに帰着する．

• $\{ 1,1,2\}, \{ 0,1,1 \}, \{ 0,1 \}$ がそれぞれ $5$ 個ずつ，計 $15$ 個の多重集合がある．これら $15$ 個から 要素を一つずつ選ぶ．選んだ要素の和が $3$ の倍数になるような選び方はいくつあるか．

これは多項式 $f(x) = (2x + x^2)^5(1 + 2x)^5(1 + x)^5$ の $x^{3n}$ $(n=0,1,2,\dots)$ の係数の総和として求められ，$\omega = \dfrac{-1 + \sqrt{-3}}{2}$ とおくと $\displaystyle \frac{1}{3} \sum_{k=0}^{2} f(\omega^{k})$ に等しい．$f(x) = (2x^4 + 7x^3 + 7x^2 + 2x)^5$ より， $$\begin{aligned} &\dfrac{1}{3} \sum_{x=1, \omega, \omega^2} (2x^4 + 7x^3 + 7x^2 + 2x)^5 \\ &= \dfrac{1}{3} \sum_{x=1, \omega, \omega^2} (7x^3 + 7x^2 + 4x)^5 \\ &= \dfrac{1}{3} \cdot 18^{5} + \dfrac{1}{3}\sum_{x=\omega, \omega^2} (7x^3 + 7x^2 + 4x)^5 \\ &= 6\cdot 18^{4} + \dfrac{1}{3}\sum_{x=\omega, \omega^2} (-3x)^5 \\ &= 6\cdot 18^4 - 3^4\cdot (\omega^5 + \omega^{10}) \\ &= 6\cdot 18^4 + 81 \end{aligned}$$ $x_1,x_2,\dots, x_{10}$ の役割は巡回的に対称なので，$X = (2,k_2,2,k_4,2,k_6,2,k_8,2,k_{10})$ の場合も同様である．したがって Case 2. の場合は $12 \cdot 18^{4} + 162$ 組 の条件を満たす $(X,Y)$ が得られる．

　以上より，求める個数は $$3^{9}\cdot (3^{10} - 64) + (12 \cdot 18^{4} +162) = 3^{19} + 162 = \mathbf{1162261629}$$