#038 モンモール問題

問題

　6人でプレゼント交換するとき、6人とも自分のプレゼントをもらわない組み合わせは全部で何通りあるか求めよ。

イズミの解答への道

　パズルとして見れば小学生でも解けそうだが、実は場合分けも含めてかなり難しい問題です。実際、大学入試にも出題されるテーマが隠されています。

解答

解答

　n 人でプレゼント交換をして、全員が自分のプレゼントをもらわない場合の数を a_n とする。求める場合の数は a₆ である。
　
　6人に1番から6番の番号をつけ、まず1番が2番のプレゼントをもらったとしよう。このとき、

• 2番が1番のプレゼントをもらったときは、残り4人の状況を考えればよく、それは a₄ 通りである。
  
• 2番が1番以外のプレゼントをもらったとする。すると、2番～6番の人はそれぞれ 1 , 3 , 4 , 5 , 6 番のプレゼントをもらうことになるのだが、ここでトリッキーであるが、「1番のプレゼントを2番のプレゼントだと見なして」みる。なぜこれが許されるかというと、
  
  • 3番～6番の人にとって、1番のプレゼントは誰がもらってもよいプレゼントであるかり、それは2番だとしても同じことであるから問題がない。
    
  • 2番の人にとって、1番のプレゼントは貰わないと前提を立てた（下線部）ことから、1番のプレゼントを2番だと思い込むことはむしろ都合がよい
    
  からである。つまり、「1番のプレゼントを2番と思いこむ」ことは逆にちょうどよいことになる。このように読みかえると、2番～6番の人が、2番～6番のプレゼントを自分のに当たらないようにもらう場合の数を求めていることになり、それは a₅ 通りである。

　となるので、1番が2番のプレゼントをもらったとき、題意を満たす場合の数は、a₅ + a₄ である。
　
　1番が2番以外のプレゼントをもらったときも、同様に考えられるので、もとめる場合の数は、
　　　a₆ = 5×( a₅ + a₄ )
となる。
　同じ理論により、一般的に、
　　a_n = ( n – 1 ) × ( a_n-1 + a_n-2 )
が成り立ち、a₂ = 1 , a₃ = 2 であるから、あとはこの式によって、
　　a₄ = 3 × ( 2 + 1 ) = 9 , a₅ = 4×( 9 + 2 ) = 44 ,
　　a₆ = 5×( 44 + 9 ) = 265
となり、 265 通りが正解である。

研究

モンモールの問題

　1 , 2 , … , n の順列 a₁ , a₂ , … , a_n のうち、すべての k （ 1 ≦ k ≦ n ）に対して、 a_k ≠ k を満たす順列の個数をモンモール数といい、この順列を完全順列などという。
　
　モンモール数については、今回の解答のなかで一般化した
　　　a_n = ( n – 1 ) × ( a_n-1 + a_n-2 )　（ n ≧ 3 ）
が成り立つ。ただし、a₂ = 1 , a₃ = 2 である。
　
　モンモール数については、問題の中身が簡潔な割に式が立てにくい問題であることで有名であり、この漸化式の立て方は一度経験していないと思いつくのはかなり難しい。
　しかしながら、モンモールの問題は大学入試でもよく出題されており、もっとも難しいのはこの漸化式を証明する

• 完全順列［2004 東工大（後）］

の問題である。こちらも参考にしてもらいたい。