MathLabs

第6問

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

第一ブロックの選択元を全てずらしても個数は保たれ、pp 回で元に戻る。

T↦T+1(modp)T\mapsto T+1\pmod p
詳しい解説

{p+1,…,2p}\{p+1,\ldots,2p\} との共通部分を固定し、第一ブロックの rr 個の選択を {1,…,p}\{1,\ldots,p\} 上で T↦T+1(modp)T\mapsto T+1\pmod p により巡回シフトする。0<r<p0<r<p なので非零シフトは TT を固定せず、各軌道は pp 個の相異なる集合からなる。各シフトで第一ブロックの和は rr だけ mod pp 増加する。