整数問題〜苦手な人のために考え方をレクチャー〜

整数問題には作戦がいくつかあります。

よく用いられるのが、以下の３つです。

1,不等式で評価する

2,合同式(mod)を用いる

3,場合の数に帰着する

さて、2,合同式の話は大変なので、1,3のお話を例題を出してみていきます。

例題

x,y,zを0以上の整数とする。

x+y+z=6となるような(x,y,z)の組は何組あるか？

方針1(不等式で評価して全部数えちゃおう作戦) 

ちょっと工夫して全部数えちゃいましょう。

考える方程式は対称式なので、x≦y≦zとしても一般性を失わないことに注意して、数え上げましょう。

解

x+y+z=6は対称式なので、x≦y≦zとしても一般性を失わない。すると、

3x≦x+y+z=6よりx≦2

すなわちx=0,1,2

(i)x=0の時

6=y+z≧2yよりy≦3

すなわちy=0,1,2,3

ーやってたらきりがないので省略ー

まあ、つまりこの作戦はそこそこ大変なのです。。

方針2(場合の数に帰着作戦)

○６つと棒2つを並べる順列とx＋y＋z＝6の解は一対一に対応する。

〜解説〜

どういうことかと言うと、

x=1,y=0,z=5⇄○||○○○○○

x=2,y=1,z=3⇄○○|○|○○○

といった感じに対応する。

わからない人のためにもっと詳しく書けば

一本目の棒の左側にある○の個数がx

一本目の棒と二本目の棒の間にある○の個数がy

二本目の棒の左側にある個数がz

に対応する。

〜解説おわり〜

よって、(x,y,z)の組は8_C_2=28個。