ｸｲｽﾞ大陸

あらら、閉めちゃいましたか．確かにこの辺りを知っている者には、ほとんど直感的に
分かる問題ですが，高校生にも分かるように書くとなると、そう簡単ではありません．
ここ数日忙しくて、書く気力がなかったのですが、答えだけでも書いておくのでした．
では、米スロベニア戦を見ながら (終わった)，問題の書き換えと証明をしておきます．
ただし、B = Sym(F_p) としています．

問　題

３以上の素数を p として、(整数を p で割った余りの) 集合 F_p = {0, 1, ..., p-1}
を考える．F_p 要素を並び替えた任意の順列 f = (f(0), f(1), ..., f(p-1)) について、
集合 A_f = {x f(x) mod p | x ∈ F_p} を作るとき、A_f の濃度（要素数）|A_f| の
最大値を求めよ．もちろん、複数の同じ値があれば、１個と数える．

解　答：　max |A_f| = p - 1．

　証　明

以下の３つの事実から明らかである．

f(0) ≠ 0 のとき |A_f| ≦ p - 1.

x ≠ 0, f(x) = 0 なる x が存在するので、0 f(0) = x f(x) = 0 であるから、
|A_f| ≦ p - 1.

f(0) = 0 のとき |A_f| ≦ p - 1.

ただちに分かるように，任意の x ≠ 0 について f(x) ≠ 0 である．
　ここで、{1, 2, ..., p-1} の相異なる要素の任意の組 (x, y) に対し，
x f(x) mod p ≠ y f(y) mod p が成立すると仮定すれば、
1 f(1)・2 f(2)・...・(p-1) f(p-1) mod p = (p-1)! mod p である．
　一方、1 f(1)・2 f(2)・...・(p-1) f(p-1) = (p-1)!・(p-1)! であるから、
(p-1)! mod p = 1 を得るが、これは、Wilson の定理　(p-2)! mod p = 1 に反する．
　したがって、少なくとも１組は x f(x) mod p = y f(y) mod p なる (x, y) が
あるので、|A_f| ≦ p - 1.

|A_f| = p - 1 なる f が存在する

任意の x ≠ 0 について、x y mod p = 1 を満たす y が唯一存在するので、
この y を x^(-1) と書く．
　いま、f(0) = 0, f(1) = 1 とおき、それ以外の x (2 ≦ x ≦ p-1) について
f(x) = 1 - x^(-1) mod p とする．明らかに 2 ≦ x^(-1) ≦ p-1 であるから、
2 ≦ f(x) ≦ p-1 であり、かつ、互いに等しくない．
　すなわち、f は F_p の順列の１つであり、1 ≦ x f(x) = x - 1 ≦ p-2 を満たす．
よって、１だけが重なるから、|A_f| = p - 1 である．

終わりに

Wilson の定理や x^(-1) の存在についての説明は省略しました．
ネットや本で調べて下さい．ご要望があれば、説明をしても構いません．