OMCE004(D)

　$$\sum_{k = 0}^{1012} 2024^ {1012-k} x^{2k} = \dfrac{x^{2026} - 2024^{1013}}{x^{2} - 2024}$$ であるため，$ω = \cos \dfrac{2\pi}{2026} + i \sin \dfrac{2\pi}{2026}$ とおくと，方程式が持つ $2024$ 個の複素数解は $$\pm \sqrt{2024} × ω^{k} \quad (1 \leq k \leq 1012)$$

と表されることが分かる．ここで，$ω^{k}$ が実数になるための必要十分条件は，$\dfrac{2k}{2026} = \dfrac{k}{1013}$ が整数になること，すなわち $k$ が $1013$ の倍数になることであり，また, $|ω^{k}| = |ω|^{k} = 1$ であることから，これは $\omega^k$ が整数になるための必要十分条件であることも分かる．また, $\sqrt{2024}$ が無理数であることから，この問題は次のように言い換えられる．

• 全部で $2024$ 枚のカードがあり，それぞれには $1$ つずつ整数が書かれている．また, $1$ から $1012$ までの全ての整数について，それが書かれたカードは $2$ 枚ずつ存在する．全てのカードを区別するとき，これらのカードの中から $1$ 枚以上かつ偶数枚選んで書かれた整数の和が $1013$ の倍数になるようにする方法は何通りあるか？

　まず，$1$ 枚以上という条件をなくして考える．カードを偶数枚選んで和が $1013$ の倍数になるようにする場合の数を $A$，奇数枚選んで和が $1013$ の倍数になるようにする場合の数を $B$ とする．このとき，$A+B$ は $$\sum_{n = 0}^{\infty} \ [x^{1013n}] \ (x + 1)^{2}(x^{2} + 1)^{2}\cdots(x^{1012} + 1)^{2}$$ と表されることが分かる．また，$A-B$ は $$\sum_{n = 0}^{\infty} \ [x^{1013n}] \ (x - 1)^{2}(x^{2} - 1)^{2}\cdots(x^{1012} - 1)^{2}$$ と表されることも分かる ( $-1$ が選ばれる回数を考えることにより，$B$ に対応する項のみがすべて $-1$ 倍されることを確認せよ)．ただし多項式 $p$ と非負整数 $d$ について $[x^d]p(x)$ で $p(x)$ の $x^d$ の係数を表す．以下 $$f(x) = (x + 1)^{2}(x^{2} + 1)^{2}\cdots(x^{1012} + 1)^{2}$$ $$g(x) = (x - 1)^{2}(x^{2} - 1)^{2}\cdots(x^{1012} - 1)^{2}$$ とする．ここで，$ω^{\prime}$ を $ω^{\prime} = \cos \dfrac{2\pi}{1013} + i \ \sin \dfrac{2\pi}{1013}$ で定めたとき，整数 $k$ に対して $$1+{ω^{\prime}}^{k}+{ω^{\prime}}^{2k}+\cdots+{ω^{\prime}}^{1012k} = \begin{cases} 0 & (1013 \nmid k) \\ 1013 & (1013 \mid k) \end{cases}$$ であることから， $$A+B = \dfrac{1}{1013} \left( f(1) + f(ω^{\prime}) + f({ω^{\prime}}^{2}) + \cdots + f({ω^{\prime}}^{1012}) \right)$$ $$A-B = \dfrac{1}{1013} \left( g(1) + g(ω^{\prime}) + g({ω^{\prime}}^{2}) + \cdots + g({ω^{\prime}}^{1012}) \right)$$

が成り立つことが分かる．いま， $$F(x) = (x - ω^{\prime})(x - {ω^{\prime}}^{2})\cdots(x - {ω^{\prime}}^{1012}) = x^{1012} + x^{1011} + \cdots + x + 1$$ と定義すると，整数 $1 \le k \le 1012$ に対して $f({ω^{\prime}}^{k}) = F(-1)^2 = 1$ および $g({ω^{\prime}}^{k}) = F(1)^2 = 1013^2$がわかる．これと $f(1) = 2^{2024}, g(1) = 0$ を合わせて， $$A+B = \dfrac{2^{2024} + 1012}{1013}, \quad A-B = 1012 \cdot 1013$$ がわかるので， $$A = \dfrac{1}{2026} × (2^{2024} + 1012 + 1012 × 1013^{2})$$ が従う．カードを一枚も選ばない場合を除かなくてはいけないため，求めるべきは $A-1$ を $1009$ で割った余りであり，フェルマーの小定理を用いるなどすればこれは $\mathbf{668}$ と分かる．