MathLabs

第6問

pp を奇素数とする。{1,2,…,2p}\{1,2,\ldots,2p\} の pp 元部分集合 AA で、その元の和が pp で割り切れるものはいくつあるか。
ステップ 1/3: 二つの例外集合を除く
ざっくり言うと

最初のブロック全体と後半ブロック全体は既に解で、軌道が固定される。

(2pp)−2\binom{2p}{p}-2
詳しい解説

(2pp)\binom{2p}{p} 個の pp 元部分集合がある。{1,…,p}\{1,\ldots,p\} と {p+1,…,2p}\{p+1,\ldots,2p\} を除くと、どちらも和が pp で割り切れる。残りの集合では第一ブロックから選ぶ個数を rr とし、0<r<p0<r<p である。