OMC217(C)

　$T\subset S$ に $3$ の倍数が含まれるとき，$f(T) = 0$ である．
　次に，$T\subset S$ に $3$ の倍数が含まれない場合を考える．このとき，次が成り立つ．

• $T$ に $3$ で割って $2$ あまる数が偶数個含まれているなら $f(T) = 1$，奇数個含まれているなら $f(T) = 2$．

したがって， $$A = {}_{3000}\mathrm{C}_{0} + {}_{3000}\mathrm{C}_{2} + \cdots + {}_{3000}\mathrm{C}_{3000},\quad B = {}_{3000}\mathrm{C}_{1} + {}_{3000}\mathrm{C}_{3} + \cdots + {}_{3000}\mathrm{C}_{2999}$$ とおくと，$f(T) = 1$ となるような $T\subset S$ の数 $n_1$，$f(T) = 2$ となるような $T\subset S$ の数 $n_2$ はそれぞれ $$n_1 = 2^{3000}A - 1,\quad n_2 = 2^{3000}B$$ と表せる．ここで，次の補題が成り立つ．

補題より，求める平均は次のように計算できる． $$\frac{1\cdot n_1 + 2\cdot n_2}{2^{9000} - 1} = \frac{3\cdot 2^{5999} - 1}{2^{9000} - 1}$$ 今，素数 $p$ が $3\cdot 2^{5999} - 1$ と $2^{9000} - 1$ を割り切ったとする．すなわち， $$3\cdot 2^{5999} \equiv 2^{9000} \equiv 1\pmod p$$ が成り立ったとする．このとき，$2^{9000} - 1$ は奇数であるから $p$ は奇素数である．また， $$3 \equiv \frac{1}{2^{5999}} \equiv \frac{2^{9000}}{2^{5999}} = 2^{3001} \pmod p$$ が成り立つ．したがって， $$27 = 3^3 \equiv (2^{3001})^3 = 8\cdot 2^{9000} \equiv 8 \pmod p$$ であるから，$p = 19$ である．一方で，フェルマーの小定理より $3\cdot 2^{5999} - 1$ と $2^{9000} - 1$ はともに $19$ で割り切れる．また，LTEの補題より $2^{9000} - 1$ は $19^2$ で割り切れないことが確認できるので， $$b = \frac{3\cdot2^{5999} - 1}{19}$$ である．これを $2999$ で割ったあまりは，$\bf2211$ である．