今回のテーマは「モンモール問題」
問題
6人でプレゼント交換をするとき
自分のプレゼントを貰わないやり方は何通り？
これは完全順列の問題ですね……と思ったら解説で出てきた。
学生時代に一度痛い目にあっているので、
やり方を完全に覚えていた問題です。
2人のとき、3人のときが何通りあるかを考え、
そこから4人、5人と発展させていく過程で
ある法則性が見つけられればこの問題は解けます。
大学入試にも出る位の問題ですから、
高校生レベルの知識量で何とかなってしまいます。
問題は漸化式を作る部分なんでしょうけど……
n人のときの方法をf(n)通りとして、以下の漸化式が成り立ちます。
f(n+2) = (n-1){f(n+1) + f(n)}
3項間漸化式ですから、ここから一般項を求めるのも
高校レベルの問題という事で、今回はちょっと簡単だったかな。
相変わらず力技で数え上げるコマ大数学部は凄いと思いましたが……
数え上げをミスしないのって意外に難しいんですけど。
PR
