はじめに.
高校数学の話(特に組合せ論の話)。この記事では1対1の対応について考える。最終的に以下の問題に答えを与える。以下では正整数a,非負整数bに対して(a choose b)を(a|b)と表すことにする。
<組合せの復習①>
問題1. a+b+c=5を満たす非負整数の組(a,b,c)は何通りあるか？
(非負整数は0以上の整数のことです)
解答1. 題意の組としてあり得るのは(a,b,c)=(5,0,0),(4,1,0),(4,0,1),(3,2,0),(3,0,2),(3,1,1),(2,3,0),(2,0,3),(2,2,1),(2,1,2),(1,4,0),(1,0,4),(1,3,1),(1,1,3),(1,2,2),(0,5,0),(0,0,5),(0,4,1),(0,3,2),(0,2,3),(0,1,4)の21通りである。
愚直に数える方法。大変。
解答2. 5つの○と2つの|を一列に並べて以下のように(a,b,c)に対応させる。
このようにして(a,b,c)を数え上げることができ、答えは(7|2)=21通り。
典型問題。解答1より簡単。
<組合せの復習②>
問題2. a+b+c=5を満たす自然数の組(a,b,c)は何通りあるか？
解答. 題意の組としてあり得るのは(a,b,c)=(1,1,3),(1,2,2),(1,3,1),(2,1,2),(2,2,1),(3,1,1)の6通り。
右辺の数が小さいことと、a,b,cが自然数であるという制約によって、数え上げる解法が有効に刺さる。では次の問題はどうか。
問題3. a+b+c=100を満たす自然数の組(a,b,c)は何通りあるか？
右辺の数が大きいので数え上げるのが大変。そこで問題1での解法2のような工夫した数え上げができないかを考える。
解答. a+b+c＝100は(a-1)+(b-1)+(c-1)=97と同値である。a,b,cはそれぞれ1以上の自然数なので(a-1),(b-1),(c-1)は非負整数。したがって97つの○と2つの|を並べて、問題1の解答2でしたように、○の個数を(a-1),(b-1),(c-1)に対応させることにより、求めるべきは(99|2)=4851通りと分かった。
解答が分かりにくい方へ。例えば(a-1,b-1,c-1)=(13,45,39)と(a,b,c)=(14,46,40)がリンクしている。また(a-1,b-1,c-1)=(0,1,96)と(a,b,c)=(1,2,97)がリンクしている。このように上手く(a,b,c)が自然数の組になるようにしている。(このような解法が有効な理由は後から述べることにする。)
一般化してみよう。
問題4. nを3以上の整数とする。a+b+c=nを満たす(a,b,c)の組は何通りあるか？
解答. やはり与式は(a-1)+(b-1)+(c-1)=n-3と同値である。(a-1),(b-1),(c-1)はそれぞれ非負整数より、n-3つの○と2つの|を並べて、適当に対応させることにより(n-1|2)=(n-1)*(n-2)/2通りを得た。
nが登場しようと何てことはない。
<1対1の対応について①>
ようやく本題に入っていく。
問題5. 整数の組(x,y)がy=x^2を満たしている。y<=9を満たす(x,y)の組は何通りあるか？
解答. x^2=y<=9から-3<=x<=3。またこれを満たす整数xに対しyも確かに整数値をとるので答えは7通り。
では以下に誤りの解答を載せるので誤りを指摘せよ。
(誤)解答. yは整数で平方数である。9以下の平方数は0,1,4,9より答えは4通り。
なぜ正しく数えられなかったのだろうか。
例えばy=9に対して整数の組(x,y)は(3,9),(-3,9)が存在する。これを考えるとyの個数を単純に数えただけでは整数解を全て網羅できない。一方xを先に決めたときは上手くいく。これはxを一度決めればyの値も1つに定まるからだ。
問題6. 整数の組(x,y)がy=2^xを満たしている。y<=4を満たす(x,y)の組は何通りあるか？
解答1. 2^x=y<=2^2とy=2^xは(狭義)単調増加だからx<=2を得た。x=0,1,2に対しyも確かに1つの整数値をとるので求める組合せは3通り。
解答2. yは2冪であるから、y<=4がとり得る値はy=1,2,4のいずれか。逆にy=1,2,4の各yに対してxも一意に整数値をとるので答えは3通り。
今度はxから求めても、yから求めても上手くいった。これはxを決めるとyがただ1つに定まるし、逆にyを決めてもxが1つに定まるからだ。つまりxとyには1対1の対応が見られる。y=x^2とy=2^xの違いに注意せよ。
<1対1の対応について②>
さて1対1の対応があると何が嬉しいのだろうか。例えば(a,b,c)の組合せと(a',b',c')に1対1の対応があると仮定する。このとき対応があるおかげで、(a,b,c)の組合せが知りたいときに(a',b',c')の組合せを考えればよくなる。(a,b,c)の組合せを直接求めるのが困難だとしても、(a',b',c')の組合せが楽に求められたら計算の負担を減らすことができる。ここにおいて、問題3を再び見よう。
問題3. a+b+c=100を満たす自然数の組(a,b,c)は何通りあるか？
問題の状況そのままだと○と|を用いた解法を適用するのが難しい。ところが与式を(a-1)+(b-1)+(c-1)=97と見てみると、その典型的な解法を用いることができそうだ。当然aを1つ決めるとa-1も値が1つに決まるし、a-1を決定してもaが一意に定まる。b,cの場合も同様なので、求める組合せは(a-1)+(b-1)+(c-1)=97を満たす(a-1,b-1,c-1)の組合せに帰着された。この議論は重要なので解答でも対応があることを明示するのが良い。
解答(改). a+b+c＝100は(a-1)+(b-1)+(c-1)=97と同値である。aに対しa-1は一意だし逆も同様。b,cについても同じことが言えるので、自然数(a,b,c)の組合せは非負整数(a-1,b-1,c-1)の組合せに帰着された。したがって97つの○と2つの|を並べて、問題1の解答2でしたように、○の個数を(a-1),(b-1),(c-1)に対応させることにより、求めるべきは(99|2)=4851通りと分かった。
<1対1の対応について③>
いよいよ最後の問題。
問題7. 1≦i<j<k≦5となるように整数の組(i,j,k)を選ぶ方法は(5|3)=10通りある。一方この(i,j,k)に対してa=j-i,b=k-j,c=5+i-kとするとa,b,cは正整数となりa+b+c=5を満たす。ここでa+b+c=5を満たす正整数(a,b,c)の組合せを求めると(4|2)=6通りである。なぜ場合の数が一致しなかったのか理由を述べよ。
最初に提起した問題。ここまで説明したことを思い出して理由を考えてみよ。下はヒント。
ヒント1. (a,b,c)に色々代入せよ。
ヒント2.
ヒント1と似ていますが、こちらのヒントの方が核心をついている。
解答.
解説. まず1<=i<j<k<=5なる(i,j,k)を1つ決めるとa=j-i,b=k-j,c=5+i-kのように(a,b,c)がただ1つに決まることは良い。問題はその逆。ヒントや解答で述べたように、a=1,b=c=2を代入して整理してみよう。するとj-i=1,k-j=2,k-i=3となりますが、(i,j,k)=(2,3,5),(1,2,4)のように解が複数見つかってしまった。すなわち(a,b,c)を1組固定しても、それに対応する(i,j,k)は1組だけとは限らない。よって(a,b,c)と(i,j,k)の間に1対1の対応がないのでそれぞれ別の組合せを求めていたという感じである。
以上。1対1の対応が云々と言及する数学の問題集は意外と少ない。俺は大数(大学への数学)くらいでしか見たことがない。しかし対応の有無で組合せを上手いこと言い換えられるかどうかというクリティカルな問題に関わってくるので、記事にまとめてみた。
