プロが教える店舗&オフィスのセキュリティ対策術

nを自然数とする。
n人に招待状を送るため、宛名を書いた招待状と、
それを入れる宛名を書いた封筒を作成した。
招待状を全部間違った封筒に入れる方法がa[n]通りあるとする。
任意の素数pに対してa[p+1]がpで割り切れることを証明せよ。

という問題なのですが、教えてほしいです。お願いします。

A 回答 (2件)

←No.1


そのやり方では、n枚目の封筒に入れる招待状が
正しいものしか残ってない場合が考慮されていない。
a[n] は、ほんとはこうなる↓
https://manabitimes.jp/math/612

この式を mod p で考えると、
a[p+1] = Σ[k=2..p+1] ((p+1)!/k!) (-1)^k
   ≡ Σ[k=p..p+1] ((p+1)!/k!) (-1)^k ; k が小さい間は約分して分子に p が残る
   = ((p+1)!/p!) (-1)^p + ((p+1)!/(p+1)!) (-1)^(p+1)
   = (-1)^p { (p+1) + (-1) }
   = (-1)^p { p }
   ≡ 0 (mod p).
    • good
    • 0
この回答へのお礼

解決しました

なるほど…!!
ありがとうございました。

お礼日時:2021/05/22 19:50

n人とする。


1人目を間違うのは(n-1)通り [自分以外はn-1
2人目を間違うのは(n-2)通り [残ったn-1人で、自分以外はn-2


a[n]=(n-1)(n-2)・・・・・1

p+1人ではn=p+1を代入すれば
a[p+1]=p(p-1)(p-2)・・・・・1

因数にpがあるから、pで割り切れる
    • good
    • 0
この回答へのお礼

うーん・・・

1人目の招待状が2人目の封筒に入った場合は、
2人目はn-1通りではないでしょうか?

お礼日時:2021/05/22 17:09

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人はこんなQ&Aも見ています


このQ&Aを見た人がよく見るQ&A

人気Q&Aランキング