問題30：Poland MO 2018

#30

組み合わせ

★★★☆☆

Poland MO 2018 問6

$p$ を $5$ 以上の奇素数とする. $1, 2, \dots, p$ の並べ替え $(a_{1}, a_{2}, \dots, a_{p})$ であって, $a_{1} a_{2} + a_{2} a_{3} + \dots + a_{p - 1} a_{p} + a_{p} a_{1}$ が $p$ の倍数であるようなものの総数を $K$ とおく. このとき, $K + p$ は $p^{2}$ の倍数であることを示せ.

解いてみた

平山：おもしろそう
兒玉：たのしそう
渡辺：わああい
宿田： $K$ は $p$ の倍数(当たり前)
平山：もうどこか固定しちゃっていいよね
兒玉：さすがに $p$ 固定しない？
平山： $a_{1} a_{2} + \dots + a_{p - 2} a_{p - 1}$ なる置換が $K^{'}$ 通りとして
平山： $K^{'} + 1$ が $p$ の倍数ってことか
渡辺：原始根を見ている
馬杉：見たくねー
兒玉：そんなに悪くはなさそう
平山：まあ確かに素数の使い道ってなったときに…
馬杉：Wilsonの定理とかあるだろ！！！
平山：確かに $(p - 1)! + 1$ って $p$ の倍数なんですよね、だからどうなる…
馬杉：でもとりあえず総数は知りたくなるじゃん
馬杉：というか $0$ 以外の定数倍しても条件保たれるじゃん
平山： $K^{'}$ は $p - 1$ の倍数だね
馬杉：でもあまりうれしさを感じないデータ
兒玉： $(a_{i} + a_{i + 1})^{2}$ の形にして和を考えるとか
平山：でも置換であるって条件が見えにくくなる気がします…
馬杉： $a_{1} a_{2} + \dots + a_{p - 2} a_{p - 1} \equiv 1 (m o d p)$ なるやつが $p$ の倍数個あってほしくて
平山：それかなり良さそう
馬杉：でも進展ない、全部違うって条件がキツい
兒玉：そもそも $(p - 1)!$ が $p$ の倍数じゃない時点でつらくて
馬杉：あっ、全部に $1$ 足したらどうよ
平山：同じ数足しても条件保たれるのか
兒玉：同じ順列に戻ってくるケースがある
宿田： $31420 \to 42031$ みたいなのかな
馬杉：できた気がする、 $(a_{1}, \dots, a_{p})$ に対して $(a_{i} + j, a_{i + 1} + j, \dots)$ みたいなものを考えると
馬杉：基本的に $p^{2}$ 個で、例外処理は等差数列の場合にのみ起こる
兒玉：よさそう
馬杉：逆に等差数列は常にそうで、それは $p (p - 1)$ 個ある、おわり！
宿田：おー
渡辺：はい天才
平山：定数倍は使わないのか…
馬杉：これ固定を外しにいくのが心理的な盲点っぽい、それっぽいから
平山：対称性が、一番やな！！

解説・感想

$m o d p$ の乗法における周期と加法における周期があって, 後者の気持ちで解かないといけなかった
必要に応じて崩す必要こそあれ, 対称性はやはり基本的に保ちたい性質

解答

以下すべての合同式は $mod p$ で考え, $\sum$ は $i = 1$ から $p$ までとる. また任意の $i$ に対し $a_{p + i} = a_{i}$ とする.

二つの順列 $(a_{1}, \dots, a_{p}), (b_{1}, \dots, b_{p})$ に対して, 次の関係を考える.

ある $k, l$ が存在して任意の $i$ に対して $b_{i} \equiv a_{i + k} + l$ をみたす.

順列 $X$ と $Y$ , $Y$ と $Z$ が条件を満たすならば $X$ と $Z$ も条件をみたすことから, これは同値関係であり, $p!$ 通りの順列をいくつかの同値類へ分けることができる. ここで同じ同値類に含まれる二順列について $\sum a_{i} a_{i + 1}$ は $mod p$ で合同である. これは二つの順列を $(a_{1}, \dots, a_{p})$ と $(b_{1}, \dots, b_{p}) \equiv (a_{k + 1} + l, \dots, a_{k} + l)$ とすれば, 以下より従う. $\sum b_{i} b_{i + 1} \equiv \sum a_{i} a_{i + 1} + 2 l \sum a_{i} + p l^{2} \equiv \sum a_{i} a_{i + 1}$ 　さてこの分類において, ある整数 $d$ が存在して任意の $i$ について $a_{i + 1} \equiv a_{i} + d$ をみたす順列 $(a_{1}, \dots, a_{p})$ が含まれる同値類の大きさは $p$ であり, そうでない同値類の大きさは $p^{2}$ である. なんとなれば, 順列 $(a_{1}, \dots, a_{p})$ が含まれる同値類の大きさは, 以下の形で表される組 $(a_{i + 1} - a_{i}, a_{i + 2} - a_{i + 1}, \dots, a_{i} - a_{i - 1}) (m o d p) (i = 1, \dots, p)$ の種類数の $p$ 倍だからである. 前者の同値類について, 種類数は $d$ の種類数に等しく $p - 1$ であり, また $\sum i d \cdot (i + 1) d = \frac{p (p + 1) (p + 2)}{3} \cdot d^{2} \equiv 0$ であるから, これに含まれる順列は全て題意を満たす. よって後者の同値類のうち条件を満たすようなものを $A$ 個とすると, 求める順列の数は $K = p (p - 1) + p^{2} A = p^{2} (A + 1) - p$ であり, 題意は示された.