今回取り上げるのはプレゼント交換問題などと言われるものです。
中学入試では毎年数校で出るか出ないかぐらいの出題頻度にとどまりますが、初見での対応は少し難しい考え方をする(場合分けして前の結果を利用する)ため、大手進学塾のテキストでも必ず取り上げているはずです。
かくらん順列の一つのアプローチを誘導形式で求めさせる良問として、たとえば次のようなものが出されています。
生徒から1個ずつ集めたプレゼントを先生が生徒に分けることにしました。次の空らんに当てはまる数を答えなさい。(早稲田中2021)
⑴ A、B、Cの3人から集めたプレゼントを先生が分けます。
㋐ 3人とも自分のプレゼントを受け取るとき、その分け方は1通りあります。
㋑ 3人とも他の人のプレゼントを受け取るとき、その分け方は2通りあります。
㋒ 3人のうち、1人だけが自分のプレゼントを受け取るとき、その分け方は▢通りあります。
次の 3通り
その後、遅れてDがプレゼントを持ってきました。ここからDが3人のうち、誰か1人とプレゼントを交換することで4人とも他の人のプレゼントを受け取る分け方を考えます。
㋐の場合は、誰と交換しても分けられません。
㋑の場合は、A、B、Cの誰か1人と交換すれば、分けられます。
㋒の場合は、A、B、Cのうち、自分のプレゼントを受け取った人と交換すれば、分けられます。
以上のことから、4人とも他の人のプレゼントを受け取る分け方は▢通りあります。
㋑の場合(3人とも他人のプレゼントを受け取っていたとき)
このとき、Dが3人のうちの「誰か1人と交換」すればよいので、そのパターンは次の6通り。
㋒の場合(1人だけは自分のプレゼントを受け取っていたとき)
このとき、Dは「自分のプレゼントを受け取った人と交換」することになるので同じく3通り。
よって(㋐は0通りなので)「4人とも他の人のプレゼントを受け取る分け方」は以上の合計で 9通り
⑵ 4人の生徒のプレゼントを先生が分けるとき、4人のうち1人だけが自分のプレゼントを受け取る分け方は▢通りあります。
同じように、あとからやってきたDと交換するしないで考えます。
❶3人とも他人のプレゼントを受け取っていたとき
Dが誰とも交換しなければよいので、そのまま2通り。
❷1人だけは自分のプレゼントを受け取っていたとき
「自分のプレゼントを受け取った人」以外の人と交換すればよいので、太字を除く6通り。
以上の合計で 8通り
⑶ 5人の生徒のプレゼントを先生が分けるとき、5人とも他の人のプレゼントを受け取る分け方は▢通りあります。
これも、あとからEがやって来たものとして考えます。
❶4人とも他人のプレゼントを受け取っていたときに5人目のEが加わるパターン
ここまでまとめると「4人とも他の人のプレゼントを受け取る分け方」は次の9通り。
このとき、あとから来たEはどのパターンで誰とプレゼント交換しても「5人とも他の人のプレゼントを受け取る分け方」という条件に合うから、ワクの数と同じ 36通り。
❷1人だけは自分のプレゼントを受け取っていたときに5人目のEが加わるパターン
「4人のうち1人だけが自分のプレゼントを受け取る分け方」は次の8通りとわかったので、ここにEが加わることを考えると、Eは自分のプレゼントを持っている人(太字)と交換すれば条件に合うので 8通り。
以上の合計で 44通り
中学入試ではもう一つ先の n=6(265通り)までの出題例があります。番号をつけたヤギと部屋、ボールと箱の問題などで出されることもあります。