数字並べ
左図のように区分けされた10個の区画に
a1、a2、a3、a4、a5、b1、b2、b3、b4、b5
と、0から9までの数字が1個ずつ割り付けられ
ている。
ただし、任意の m、n に対して、m<n ならば、am<an 、bm<bn 、am<bm であるも
のとする。
この条件を満たすような配置の仕方は、全部で何通りあるか。
(答) 条件から、a1=0 であり、b5=9 であることは明らかである。後は、残りの数字を、
条件を満たすように順番に配置していけばよい。
いま、上段に配置済みの数字の個数を X、下段に配置済みの数字の個数を
Y とす
ると、条件から、必ず Y≦X が成り立つ。この条件を満たしながら、
(X,Y)=(0,0) ・・・何も数字が配置されていない初期状態
から始まって、例えば、(1,0)→(2,0)→(3,0)→(3,1)→・・・→(5,5)と順番に
数字を配置していけばよい。
このように考えると、求める配置の総数は、下記のような市街路において、
点A(0,0)から、点B(5,5)へ至る最短経路の本数に一致することに気が付く。
したがって、求める配置の総数は、42通りとなる。
(この場合の数について、もっと正統的に求めたい
場合は、こちらを参照)
この問題を一般化した問題:
『縦2行、横 n 列の区画に、2n 個の自然数を配置
せよ。』
が、上智大学で出題されている。受験問題集には
必ずある問題なので、目にした方も多いだろう。
平成15年6月15日付け朝日新聞朝刊に、「朝日小学生新聞」宣伝のための折り込みチ
ラシが入っていて、その中に、上と同じような問題が載っていた。
チラシの方では、縦2行、横3列に、1から6までのトランプを配置させる問題であった。解
答はホームページで発表とのことなので、早速アクセスしてみた。そこでは、トランプには、
ハートとかスペードとか、4種類あることを全く考えないで、例としてあげた場合に対しての
解答がのっていた。少し解答があやしい旨、すぐメールにて連絡した。
(なお、解答掲示は、期間限定なので、確認は、お早めに!)