第２４６問の解答

１．問題　［場合の数］

１〜１４までの数の書かれたボールが１個ずつ、全部で１４個あります。
いま、あるクラスの出席番号１番〜１２番までの生徒１２人がボールを１人１個ずつ取ります。

このとき、１２人全員が、「自分の出席番号よりもボールに書かれた数のほうが大きい」ような場合は何通りあるでしょうか。

２．解答例１（C-Dさん、糸瀬善人さん、高橋道広さん、地蔵さん、有無相生さん、M.Hossieさん、ゆんななこさん、他多数）

人数がn=１〜４までを数えてみると下図のようになります。
場合の数は、ｆn＝２nと予想されます。

参考図1

１番の人から考えていくと、例えばn＝４のとき、１番の人が５のボール、２番の人が６のボールをとってしまうと４番の人が取るボールがなくなってしまいますので単純にはいきません。

そこで、逆に最後の人から考えていくことにします。

参考図2

例えば、ｎ＝５のとき、
　５番の人が取ることができるボールは６〜７の２通り、
　４番の人は５〜７の３通りから５番の人が取ったものを除く２通り
　３番の人は４〜７の４通りから５番、４番の人が取ったものを除く２通り
　２番の人は３〜７の５通りから５〜３番の人が取ったものを除く２通り
　１番の人は２〜７の６通りから５〜２番の人が取ったものを除く２通り
となるので、結局２5＝１６通りとなります。

同様にして、ｎ＝１２のときは、２12＝４０９６通りとなります。

答：４０９６通り

以上

３．解答例２（DrKさん、小西孝一さん、うっしーさん、ちーくん、うりょさん、ちえんかん＃２期さん、他多数）

n人のときの場合の数ｆnに関して、漸化式を考えることにしましょう。
しかしながら、各人が取ることのできるボールの番号は、nが増えるにつれて増加しますので、結構面倒です。

参考図3　　

そこで、n-1人のとき、１〜n-1番目の人が取ったボールの番号をa1、a2、・・・、an-1とします。
これに対して、各人の番号と取ったボールの番号の両方を、それぞれ１加えた場合を対応させることにします。
（すなわち、a2=a1+1、a3=a2+1、・・・、an=an-1+1）

a2、a3、・・・、anは、３〜ｎ+２のn個の数からn-1個選んだことになるので、あと１個残っているものがあります。１番の人が取ることができるのは、２とその番号の２通りになります。

以上のことから、ｆn＝２ｆn-1と求まりますので、
　ｆn＝２ｆn-1＝２2ｆn-2＝２3ｆn-3・・・＝２n-1ｆ1＝２n
となります。

従って、本問ではｆ12＝２12＝４０９６通りです。