第6問

p

を奇素数とする。

\{1,2,\ldots,2p\}

の

p

元部分集合

A

で、その元の和が

p

で割り切れるものはいくつあるか。

ステップ 3/3: 各軌道の和が零の集合を数える

前のステップ次のステップ

ざっくり言うと

$p$ は素数で $r$ は mod $p$ で非零なので、 $p$ 個の和は全ての剰余になる。

2+\frac{\binom{2p}{p}-2}{p}

詳しい解説

全体の和は隣り合う軌道元ごとに $r\not\equiv0\pmod p$ だけ変わるため、 $p$ 個の和は全剰余類を一度ずつ取る。各軌道に和が $p$ で割り切れるものは一つだけ。従って例外以外は $\frac{\binom{2p}{p}-2}{p}$ 個で、二つを加えて $2+\frac{\binom{2p}{p}-2}{p}$ 。