OMC217(C) - 補足と別解

　この問題を解くためには，次の $2$ つのことを考えなければなりません．

Step.1　$f(T)=1,2$ となる部分集合の数を求める
Step.2　実際に平均を求めた後，約分する

　以下，Step.1 の補足と，Step.2 の別解を紹介します．

Step.1 の補足
　問題文中では，写像 $f$ は空集合に対して定義されていないが，$f(\phi)=1$ であると定義しよう（$0$ 個の数の積は，積に関する単位元 $1$ だと定義するのが自然である）． 　$$S_0=\lbrace 3,6,9,\cdots,9000\rbrace , S_1=\lbrace 1, 4, 7,\cdots, 8998\rbrace, S_2=\lbrace 2, 5, 8,\cdots, 8999\rbrace$$ とおく．このとき，$S$ の部分集合 $T$ が $S_0$ の要素を $1$ つでも含めば，$f(T)=0$ である．$T$ が $S_1$ の要素をどう含んでも，$f(T)$ の値には影響しない．結局 $T$ が $S_2$ の要素を偶数個含むか，奇数個含むかによって，$f(T)$ の値は $1$ か $2$ かになる．
　ここまで考察すれば，$f(T)=1$ となる場合と $f(T)=2$ となる場合が同数だろうと見当がつくかもしれない．その予想を信じれば，$f(T)=1$ となる場合の数も $f(T)=2$ となる場合の数も等しく $2^{6000}÷2$ となると考えられる（実際には，問題文に従って空集合を除くので，$f(T)=1$ となる場合の数は $2^{5999}-1$ である）．
　最後に，この予想について証明をしておく．公式解説と同様に $$A= {}_{3000} \mathrm{C}_{1}+{}_{3000} \mathrm{C}_{3}+\cdots +{}_{3000} \mathrm{C}_{2999},B= {}_{3000} \mathrm{C}_{0}+{}_{3000} \mathrm{C}_{2}+\cdots +{}_{3000} \mathrm{C}_{3000}$$ とおくとき，$A=B$ すなわち $A-B=0$ を示せばよいが，このことは $(1-1)^{3000}$ の二項展開を考えればわかる．

Step.2 の別解
　求める平均は $\dfrac{3 \cdot 2^{5999}-1}{2^{9000}-1}$ だとわかった．次なる問題は，これが約分できるか否かである．メタ的な発想をすれば，この問題の点数から考えて，きっと約分できるはずだと予想できなくもない．もっと言ってしまえば，一度 WA すれば約分できることがわかる．
　そのためには，$\gcd(3 \cdot 2^{5999}-1, 2^{9000}-1)$ を考えればよい．$2^{2999}=x$ と置いて，式を見やすくしておこう．

$$\begin{aligned} \gcd(6x^2-1, 8x^3-1)&=\gcd(8x^3-1, 8x^3-6x^2)\\ &=\gcd(8x^3-1, 4x-3)\\ &=\gcd(64x^3-8, 4x-3)\\ &\leq \gcd(64x^3-8, 64x^3-27)\\ &\leq 19 \end{aligned}$$ 　一つ目の等号は Euclid の互除法である．普通は $6x^2-1$ を残すべきだが，あとの計算でわかるように，$8x^3-1$ を残す方が $4x-3$ と相性がよい．二つ目・三つ目の等号は，一方が奇数であるから従う．また，上の式で用いている不等号は，単に大小関係を表すだけではなく，一方が他方の約数であることも含意している．
　なお，三つ目の等号から次のように変形することもできる： $$\gcd(4x^2+2x+1, 4x-3)=\gcd(5x+1,4x-3)=\gcd(20x+4,20x-15) \leq 19$$ 　実際に $19$ で割り切れるかどうかは，Fermat の小定理から確認すればよい．以下は公式解説を参照．