OMC卬高杯2(E)

　$n=2^{2020}$ とする. 総和が奇数の条件を無視すれば ${_{4n}}\mathrm{C}_{2n}$ 通りである. このうち, すべてが偶数かつ $a_{2i-1}=a_{2i}$ をみたすもの ${_{2n}}\mathrm{C}_{n}$ 通りを除き, 総和が偶数のものと奇数のものが一対一に対応することを確認しよう. 実際に, 条件「$a_{2i-1}=a_{2i}$ かつこれらが偶数である」をみたさない最小の $i$ をとれば, 以下のように対応が得られる.

• $a_{2i-1}$ が奇数のとき, $a_{2i-1} \longmapsto a_{2k-1}-1$
• $a_{2i-1}$ が偶数のとき, $a_{2i-1} \longmapsto a_{2k-1}+1$

　以下, 一般に $\dbinom{2^{m+1}}{2^m}-\dbinom{2^m}{2^{m-1}}$ が $2$ でちょうど $3m$ 回割り切れることを示せば, 求める値は $\textbf{6062}$ となることがわかる. すなわち, 示すべきことは $$\dbinom{2^{m+1}}{2^m}-\dbinom{2^m}{2^{m-1}}\equiv2^{3m}\pmod{2^{3m+1}}$$ ここで $x_i=2i-1$ およびその積 $X=x_1x_2\cdots x_{2^{m-1}}$ について, $2^{2m-1}$ を法として $$\begin{aligned} \displaystyle\sum_{i=1}^{2^{m-1}}\dfrac{X}{x_i}&=\dfrac{1}{2} \Biggl(\displaystyle\sum_{i=1}^{2^{m-1}}\dfrac{X}{x_i}+\dfrac{X}{x_{2^{m-1}-i+1}}\Biggr) \\ &=2^{m-1}\displaystyle\sum_{i=1}^{2^{m-1}}\dfrac{X}{x_ix_{2^{m-1}-i+1}}\\ &\equiv -2^{m-1}X\sum_{i=1}^{2^{m-1}}(x_i^{-1})^2 \\ &\equiv -2^{m-1}X \sum_{i=1}^{2^{m-1}}x_i^2 \\ &\equiv -2^{m-1}X\times\dfrac{2^{m-1}(2^m-1)(2^m+1)}{3} \\ &\equiv 2^{2m-2}\times\text{奇数} \\ &\equiv 2^{2m-2} \end{aligned}$$ これを利用すると $$\displaystyle2\times\Biggl(\prod_{i=1}^{2^{m-1}}(2^m+x_i)-\prod_{i=1}^{2^{m-1}}(2^m-x_i)\Biggr)\equiv 2^{3m}\pmod{2^{3m+1}}$$ 一方で $\displaystyle\prod_{i=1}^k(2^i-1)!!=A_k$ とすると, $(2^k)!=2^{2^k-1}\times A_k$ であるから $$\dbinom{2^{m+1}}{2^m}-\dbinom{2^m}{2^{m-1}}=2\times(2^m-1)!!\times\dfrac{\displaystyle\prod_{i=1}^{2^{m-1}}(2^m+x_i)-\prod_{i=1}^{2^{m-1}}(2^m-x_i)}{A_m}$$ 以上より所望の結論を得る.