|
ぽっぽ |
|
お久しぶりです！
なんとこの問題、一般のpの場合に1995年の国際数学オリンピックの最終問題に出たみたいです笑（近年の数学オリンピックの問題はもっと難易度が高めですが） 以下の解法が最も自然でしょう： {1,2,…,2p}のp個の元からなる部分集合全体をAとおきます。 Aの元に対して 1→2,2→3,…,(p-1)→p,p→1,(p+1)→(p+1),…,2p→2pで置き換えるという操作を考えます。Aの元Sに対してこの操作をk回施したものをS_kと書きましょう。 まず容易に分かるようにS_0=S_pです。 次にSが{1,2,…,p},{p+1,p+2,…,2p}と異なるとき, S_0,S_1,…,S_(p-1)の各集合の元の総和をpで割った余りが互いに相異なることがわかります。(Sに含まれる{1,2,…,p}の元の数をlとしたとき,mod pで項差がlの等差数列になるので) したがって,Aの{1,2,…,p},{p+1,p+2,…,2p}と異なる元について、その総和がpの倍数になる確率が1/pになることがわかります。以上より求める結果を得ます。 他にも(x^p-1)^2を複素数の範囲で因数分解するというとてもエレガントな証明もあるようです。この方針は強力で直ちに「{1,2,…,kp}のn元部分集合」に変えた一般化も証明します。（実は最初の方針でも少し工夫するとこれを示すことが出来ます） 以下のページが参考になると思います(英語ですが) https://math.stackexchange.com/questions/314788/let-p-be-an-odd-prime-number-how-many-p-element-subsets-of-1-2-3-4-ldo |
|
10月7日（日） 12:49:20
47644 |