平成１９年４月２８日
[流れ星]
第1８９回数学的な応募問題解答
＜解答募集期間：４月８日〜４月２９日
［整数解の個数］
皆さん、大学入試問題の中で、整数解の個数を数える問題があります。
問題１：１≦ｘ１＜ｘ２＜ｘ３≦１０を満たす整数解の組は何組か。
問題２：１≦ｘ１≦ｘ２≦ｘ３≦１０を満たす整数解の組は何組か。
問題３：ｘ１＋ｘ２＋ｘ３＝１０を満たす自然数解の組は何組か。
問題４：ｘ１＋ｘ２＋ｘ３＝１０を満たす負でない整数解の組は何組か。
問題５：１≦ｘ１≦ｘ２≦ｘ３≦ｘ４≦ｘ５≦ｘ６≦６ かつ
１≦ｘ１，２≦ｘ２，３≦ｘ３，４≦ｘ４，５≦ｘ５，６≦ｘ６ を満たす整数解の組は何組か。
ＮＯ１「uchinyan」04/08 14時10分受信
04/14 13時13分受信 更新4/29
＜コメント：第１８９回数学的な応募問題への解答 改訂版を送ります。
問題5：の説明を，この方がマシかなぁという感じに，少し変えました。＞
第１８９回数学的な応募問題
［整数解の個数］
問題1：
1 <= x1 < x2 < x3 <= 10 の x1，x2，x3 は，1 〜 10 の異なる三つの整数を取ってきて小さい順に並べればいいので，
10C3 = (10 * 9 * 8)/(3 * 2 * 1) = 120 組。
問題2：
1 <= x1 <= x2 <= x3 <= 10 の x1，x2，x3 は，1 <= y1 =
x1 < y2 = x2 + 1 < y3 = x3 + 2 <= 12 との
一対一対応を考えるといいです。
y1，y2，y3 の解の個数は問題1：と同様に 12C3 で，一対一対応なので，
x1，x2，x3 の個数も 12C3 = (12 * 11 * 10)/(3 * 2 * 1) = 220 組。
問題3：
10 個の球を三つの異なる箱に少なくとも一つずつ入るように分けることと同じです。
三つの異なる箱に分けるのは，10 個を並べておいて二つの区切りを入れる，と考えればいいです。
少なくとも一つずつ入っているようにするには，最初に一つずつ入れておけばいいです。
つまり，10 - 3 = 7 個の球を三つの異なる箱に分ければいいです。
したがって，7 個の球を二つの仕切りで分ければいいので，(7+2)C2
= 9C2 = (9 * 8)/(2 * 1) = 36 組。
問題4：
これは問題3：と同様で，10 個の球を三つの異なる箱に分けることと同じです。
しかも，今回は箱には入っていない場合を許すので，そのまま，(10+2)C2 = 12C2 = (12 *
11)/(2 * 1) = 66 組。
問題5；
これは少し複雑です。次のように考えてみます。
x1 から順番に x6 までを取っていくとします。
今，x1 <= x2 <= ... <= xn = k. 1 <= x1, 2
<= x2, ..., n <= xn の場合の数を a(n,k) とします。
ただし，n <= k です。また，最終的に求めるのは，a(6,6)
です。
すると，a(n,k) は，x_(n-1) = k, k-1,
k-2, ..., n-1 までに対する
a(n-1,k), a(n-1,k-1), a(n-1,k-2), ..., a(n-1,n-1) を加えたものになります。
ところが，xn = k-1 を考えると，a(n-1,k-1)
+ a(n-1,k-2) + ... + a(n-1,n-1) = a(n,k-1) なので，
結局，a(n,k) = a(n-1,k) + a(n,k-1) です。
ただし，k = n では a(n,n-1) は意味がありませんが，形式的に，
a(n-1,k-1) + a(n-1,k-2) + ... + a(n-1,n-1) のことと解釈することにします。
これを踏まえて，横に x1 〜 x6 を取り，縦にそれまでの取りえる場合の数を書いていきます。
まず，簡単のために x1, x2 で考えてみると
x1 は，1 の場合が 1 通り，2 の場合が 1 通り。
x2 は，x1 = 1 の場合の x2 = 2 と x1 = 2 の場合の x2 = 2 で 2 通り。
これを，
..x1.x2
2:1->2->2
1:1->1
と書きます。ここで，2: と x2 とが交差するところで 2 となっているのは，
x2 = 2 の場合(x2 と 2: の交点，a(2,2))が，
x1 = 1 の場合(x2 と 1: の交点，a(2,1)，これは a(1,1) と同じ)と x1 = 2 の場合(x1 と 2: の交点，a(1,2))
の両方の和であることを示しています。
また，2: の一番右端の 2 は，最終的に求める値 a(2,2) を再度示しています。(形式的には，a(3,2))
同様に，x1，x2，x3 では，
..x1.x2.x3
3:1->3->5->5
2:1->2->2
1:1->1
これを x1 〜 x6 まで続けると，
..x1.x2.x3..x4..x5..x6
6:1->6->20->48->90->132->132
5:1->5->14->28->42->42
4:1->4->9-->14->14
3:1->3->5-->5
2:1->2->2
1:1->1
そこで，132 組になります。
(考察)
問題1：〜問題4：は，省略しますが，一般化は容易です。
問題5：も，これは，平面上の n * n の格子を対角線をまたがずに行く場合の数と同じなので，カタラン数ですね。
これも一般式はよく知られています。例えば，http://aozoragakuen.sakura.ne.jp/taiwa/node85.html
など。
なお，これは問題の趣旨ではないでしょうが，プログラムを組んでも簡単にできます。
(感想)
問題5：の解答の説明とカタラン数のことをもう少しチャント書こうかとも思ったのですが，
それなりに有名ですので手を抜いてしまいました。ごめんなさい。
ＮＯ２「ｽﾓｰｸﾏﾝ」 04/08 15時12分受信
更新4/29
こんにちは。今回も考え易い問題にてチャレンジしてみました。
問題１：１≦ｘ１＜ｘ２＜ｘ３≦１０を満たす整数解の組は何組か。
1-2-3〜10・・・8個
1-3-4〜10・・・7個
・
・
・
1-9-10・・・1個
2-3-4〜10・・・7個
・
・
・
で、結局、、、
Σ(8〜1)+Σ(7〜1)+・・・+Σ(1)=36+28+21+15+10+6+3+1=120
04/08 22時29分受信 更新4/29
再考しました。Orz〜
問題２：１≦ｘ１≦ｘ２≦ｘ３≦１０を満たす整数解の組は何組か。
問題1と同じように考えればよかったんだ、、、
1-1-1~10 ・・・10
1-2-2~10 ・・・9
1-10-10 ・・・1
2-2-2~10 ・・・9
・
・
・
Σ(1~10)+Σ(1~9)+・・・+1=55+45++120=220
問題３：ｘ１＋ｘ２＋ｘ３＝１０を満たす自然数解の組は何組か。
(x1-1)+(x2-1)+(x3-1)=7
3H7=9C7=9*8/2=36
あっそうか、、、x1~x3 まで大小の順序は関係無いんだ。^^;
問題４：ｘ１＋ｘ２＋ｘ３＝１０を満たす負でない整数解の組は何組か。
3H10=12C10=12*11/2=66
これも同じく順番は関係なかったですね ^^; Orz
問題５：１≦ｘ１≦ｘ２≦ｘ３≦ｘ４≦ｘ５≦ｘ６≦６ かつ
１≦ｘ１，２≦ｘ２，３≦ｘ３，４≦ｘ４，５≦ｘ５，６≦ｘ６ を満たす
整数解の組は何組か。
1-2-3-4-5-6
1-2-3-4-6-6・・・2
1-2-3-5-5-6
1-2-3-5-6-6・・・2
1-2-3-6-6-6・・・1
・・・5
1-2-4-・・・5
1-2-5-・・・3
1-2-6-・・・1
・・・9
1-3-3-・・・5
1-3-4-・・・5
1-3-5-・・・3
1-3-6-・・・1
・・・14
1-4-4-・・・5
1-4-5-・・・3
1-4-6-・・・1
・・・9
1-5-5-・・・3
1-5-6-・・・1
1-6-6-・・・1
・・・5
・・・3*14=42
2-2-3-・・・5
2-2-4-・・・5
2-2-5-・・・3
2-2-6-・・・1
・・・14
2-3-3-・・・5
2-3-4-・・・5
2-3-5-・・・3
2-3-6-・・・1
・・・14
3-3-3-・・・5
3-3-4-・・・5
3-3-5-・・・3
3-3-6-・・・1
・・・14
・・・3*14=42
4-4-4-・・・5
4-4-5-・・・3
4-4-6-・・・1
・・・9
5-5-5-・・・3
5-5-6-・・・1
・・・4
6-6-6-・・・1 ・・・1 ・・・14
合計=7*14=98
地道に計算しました・・・^^;;
＜水の流れ：まだ正解にいたっていません＞
ＮＯ３「Toru」 04/10 13時36分受信 更新4/29
第１８９回解答を送ります。
問題５は問題を言い換えただけで、証明になっていないのですが、カタラン数については以前にも何度か出てきたト思うので今回は省略しました。重複組み合わせやカタラン数について思い出すよい機会になりました。
問題１ 10C3=120
問題２ 10H3=12C3=220
問題３ ３人に１０個のものを、一人少なくとも１つはもらうとして分配する。まず
１個ずつくばってしまって、残り７つ 3H7=9C7=9C2=36
問題４ ３人に１０個のものを分配する。3H10=12C10=12C2=66
問題５ Aを６個（A1〜A6） Bを６個 （B1〜B6） ならべて、Bkより前にあるAの数をxkとするとすると条件を満たすx1〜x６の並びは、前から数えた場合常に（Aの数）≧（Bの数）となるようなA,Bのならびと１対１対応するので
これはカタラン数になって、C(6)=12C6-12C5=132
ＮＯ４「ぐーてん」04/11 17時44分受信 更新4/29
＜コメント：いつも拝見させていただいております。前回は、期末、期初の業務に終われ、応募できませんでした。今回は、またまた難解な整数論かと思いきや、得意の順列・組合せの問題でしたので挑戦してみました。
ギャンブル好きの私にとっては、統計・確率論は他のどの数学よりも実用数学です＾＾；＞
(1) 下例のように10個の○と3本｜を使用し，各｜より左にある○の数をx1，x2，x3として表す．
例）○○｜○｜○○○｜○○○○ ：（x1，x2，x3）＝（2，3，6）
題意より，左端には必ず○が位置し，｜と｜の間には1個以上の○が必ず入る．
従って，求める整数解の組の数は，3個の「○｜」と7個の「○」を並べる方法の数に等しく，
．
(2) 同様に，10個の○と3本の｜を使用してx1，x2，x3を表すと，題意より左端には必ず○が位置し，(1)と違ってこの場合は｜と｜が隣り合ってもよい．
例）○○○｜｜○○○○○○○｜ ：（x1，x2，x3）＝（3，3，10）
左端の○は固定なので無視し，残りの9個の「○」と3個の「｜」の並び方を考えればよい．従って求める整数解の組の数は，
．
(3) 今度は，10個の○と2本の｜を使用し，各｜によって区切られる区間の中にある○の数をx1，x2，x3として表す．
例）○○｜○○○○｜○○○○ ：（x1，x2，x3）＝（2，4，4）
題意より，左右両端には必ず○が位置し，｜と｜の間には1個以上の○が必ず入る．
左端の○は固定として無視し，残りを2個の「｜○」と7個の「○」の並び方の数を考えればよい．従って求める整数解の組の数は，
．
(4) 同様に10個の○と2本の｜を使用してx1，x2，x3を表すと，題意より両端は○でも｜でもよく，また｜と｜が隣り合ってもよいので，10個の「○」と2個の「｜」の並び方の数を考えればよい．従って求める整数解の組の数は，
．
(5) 右図のように6×6マスの格子上をSからGへ最短で行く順路の数を考える．
例えば太線の場合，（2，2，5，5，5，6）を表す．
題意を満たすためには，対角線SGより右下を通らなければよい．
各格子点への順路の数を左肩に記してS側から逐次計算し，Gへ至る順路の数は132通りと求まった．
従って、求める整数解の組の数は132通り．
ＮＯ５「浜田明巳」04/12 17時31分受信 更新4/29
問題５の表す意味が分かりにくかったのですが，プログラムにして解かせてみると，すっきりしました．
問題１：１２０組
問題２：２２０組
問題３：３６組
問題４：６６組
問題５：１３２組
Option Explicit
Sub Macro1()
Dim x1 As Integer
Dim x2 As Integer
Dim x3 As Integer
Sheets("Sheet1").Select
Cells(1, 1).Value = 0
Range("A1").Select
For x1 = 1 To 10
For x2 = x1 + 1 To 10
For x3 = x2 + 1 To 10
Cells(1, 1).Value =
Cells(1, 1).Value + 1
Cells(Cells(1, 1).Value,
2).Value = x1
Cells(Cells(1, 1).Value,
3).Value = x2
Cells(Cells(1, 1).Value,
4).Value = x3
Range("B"
& Cells(1, 1).Value).Select
Next x3
Next x2
Next x1
Range("A1").Select
'
Sheets("Sheet2").Select
Cells(1, 1).Value = 0
Range("A1").Select
For x1 = 1 To 10
For x2 = x1 To 10
For x3 = x2 To 10
Cells(1, 1).Value =
Cells(1, 1).Value + 1
Cells(Cells(1, 1).Value,
2).Value = x1
Cells(Cells(1, 1).Value,
3).Value = x2
Cells(Cells(1, 1).Value,
4).Value = x3
Range("B"
& Cells(1, 1).Value).Select
Next x3
Next x2
Next x1
Range("A1").Select
'
Sheets("Sheet3").Select
Cells(1, 1).Value = 0
Range("A1").Select
For x1 = 1 To 10
For x2 = 1 To 10
x3 = 10 - x1 - x2
If x3 > 0 Then
Cells(1, 1).Value =
Cells(1, 1).Value + 1
Cells(Cells(1, 1).Value,
2).Value = x1
Cells(Cells(1, 1).Value,
3).Value = x2
Cells(Cells(1, 1).Value,
4).Value = x3
Range("B"
& Cells(1, 1).Value).Select
End If
Next x2
Next x1
Range("A1").Select
'
Sheets("Sheet4").Select
Cells(1, 1).Value = 0
Range("A1").Select
For x1 = 0 To 10
For x2 = 0 To 10
x3 = 10 - x1 - x2
If x3 >= 0 Then
Cells(1, 1).Value =
Cells(1, 1).Value + 1
Cells(Cells(1, 1).Value,
2).Value = x1
Cells(Cells(1, 1).Value,
3).Value = x2
Cells(Cells(1, 1).Value,
4).Value = x3
Range("B"
& Cells(1, 1).Value).Select
End If
Next x2
Next x1
Range("A1").Select
'
'１≦ｘ１≦ｘ２≦ｘ３≦ｘ４≦ｘ５≦ｘ６≦６ かつ
'１≦ｘ１，２≦ｘ２，３≦ｘ３，４≦ｘ４，５≦ｘ５，６≦ｘ６ を満たす整数解の組は何組か
Dim x4 As Integer
Dim x5 As Integer
Dim x6 As Integer
Sheets("Sheet5").Select
Cells(1, 1).Value = 0
Range("A1").Select
x6 = 6
For x1 = 1 To 6
For x2 = Application.Max(x1, 2) To 6
For x3 = Application.Max(x2, 3) To 6
For x4 =
Application.Max(x3, 4) To 6
For x5 =
Application.Max(x4, 5) To 6
Cells(1, 1).Value = Cells(1, 1).Value + 1
Cells(Cells(1, 1).Value, 2).Value = x1
Cells(Cells(1, 1).Value, 3).Value = x2
Cells(Cells(1, 1).Value, 4).Value = x3
Cells(Cells(1, 1).Value, 5).Value = x4
Cells(Cells(1, 1).Value, 6).Value = x5
Cells(Cells(1, 1).Value, 7).Value = x6
Range("B" & Cells(1, 1).Value).Select
Next x5
Next x4
Next x3
Next x2
Next x1
Range("A1").Select
End Sub
ＮＯ６「新俳人澄朝」04/16 16時03分受信 更新4/29
04/17 15時41分受信 更新4/29
ＮＯ７「kashiwagi｣04/18 11時07分受信 更新4/29
＜コメント：今回の問題は非常に面白いなと感じました。但し、入試の場では時間がかかりすぎ
（特に問5.）て、中々満足のいく結果には・・・・・？と思うのですが如何でございますか。
勿論、小生には分からない簡単な計算式があるのかもしれませんが・・・・。 ＞
189回問題
問1.
最初にｘ1＝1とすると、ｘ2＝2以上9までとなる。又、その各々のｘ2についてｘ3＝3以
上の数となる。即ち簡単に表に纏めると以下の様になる。即ち、1〜8までの合計であるからN(N+1)/2のNに8を代入し、36個となる。因って、ｘ1の値を2〜8まで変化させればよい。
しかも、その際ｘ3の合計は
より求められ、計算すると120組となる。
|
ｘ1 |
ｘ2 |
ｘ3 |
|
|
1 |
2 |
3〜10 |
8個 |
|
3 |
4〜10 |
7個 |
|
|
4 |
5〜10 |
6個 |
|
|
5 |
6〜10 |
5個 |
|
|
6 |
7〜10 |
4個 |
|
|
7 |
8〜10 |
3個 |
|
|
8 |
9〜10 |
2個 |
|
|
9 |
3〜10 |
1個 |
|
|
合計 |
36個 |
||
問2.
上記解答に算す3数のうちｘ1＝ｘ2＝ｘ3、ｘ1＝ｘ2、及びｘ2＝ｘ3の場合を加えれば良い。
即ち、3数が等しい10個、2数が等しい45個×2の100個を加え、220組となる。
問3.
3数は整数であるから全てが等しい場合は無く、2数が等しい場合と3数とも異なる場合しかない事が分かる。上記問1,2の結果を利用して整理すると、以下の様になる。
即ち、8組である。
|
ｘ1 |
ｘ2 |
ｘ3 |
|
1 |
1 |
8 |
|
2 |
2 |
6 |
|
3 |
3 |
4 |
|
4 |
4 |
2 |
|
1 |
2 |
7 |
|
1 |
3 |
6 |
|
1 |
4 |
5 |
|
2 |
3 |
5 |
問4.
負でない整数解とあるので、0を加えても良いことになり、以下の様になる。
即ち、14組である。
|
ｘ1 |
ｘ2 |
ｘ3 |
|
1 |
1 |
8 |
|
2 |
2 |
6 |
|
3 |
3 |
4 |
|
4 |
4 |
2 |
|
1 |
2 |
7 |
|
1 |
3 |
6 |
|
1 |
4 |
5 |
|
2 |
3 |
5 |
|
0 |
1 |
9 |
|
0 |
2 |
8 |
|
0 |
3 |
7 |
|
0 |
4 |
6 |
|
0 |
5 |
5 |
|
0 |
0 |
10 |
問5.
条件より各々の数がとれる範囲は、
1≦ｘ1≦6、2≦ｘ2≦6、3≦ｘ3≦6、4≦ｘ4≦6、5≦ｘ5≦6、ｘ6= 6 となる。但し、条件より
ｘ1= 6の時ｘ2= 2 などの値は取れない。即ち、一例を掲げると、
|
ｘ1 |
ｘ2 |
ｘ3 |
ｘ4 |
ｘ5 |
ｘ6 |
|
6 |
6 |
6 |
6 |
6 |
6 |
|
5 |
6 |
6 |
6 |
6 |
6 |
|
4 |
6 |
6 |
6 |
6 |
6 |
|
3 |
6 |
6 |
6 |
6 |
6 |
|
2 |
6 |
6 |
6 |
6 |
6 |
|
1 |
6 |
6 |
6 |
6 |
6 |
|
5 |
5 |
6 |
6 |
6 |
6 |
|
4 |
5 |
6 |
6 |
6 |
6 |
|
3 |
5 |
6 |
6 |
6 |
6 |
|
2 |
5 |
6 |
6 |
6 |
6 |
|
1 |
5 |
6 |
6 |
6 |
6 |
|
5 |
5 |
5 |
6 |
6 |
6 |
|
4 |
5 |
5 |
6 |
6 |
6 |
|
3 |
5 |
5 |
6 |
6 |
6 |
|
2 |
5 |
5 |
6 |
6 |
6 |
|
1 |
5 |
5 |
6 |
6 |
6 |
|
5 |
5 |
5 |
5 |
6 |
6 |
|
4 |
5 |
5 |
5 |
6 |
6 |
|
3 |
5 |
5 |
5 |
6 |
6 |
|
2 |
5 |
5 |
5 |
6 |
6 |
|
1 |
5 |
5 |
5 |
6 |
6 |
|
5 |
5 |
5 |
5 |
5 |
6 |
|
4 |
5 |
5 |
5 |
5 |
6 |
|
3 |
5 |
5 |
5 |
5 |
6 |
|
2 |
5 |
5 |
5 |
5 |
6 |
|
1 |
5 |
5 |
5 |
5 |
6 |
次にｘ2を4,3,2と変化さえる。その後はｘ3変化させる。これを繰り返し、求めるものは132組となる。
ＮＯ８「kasama」 04/18
15時02分受信 更新4/29
|
【問題１】例えば、1〜10の番号を書いたボールを並べて、その中から3つ選ぶのと同じなので、 |
|
【問題２】問題１のケース数に、x1＝x2＜x3、x1＜x2＝x3、x1＝x2＝x3のケース数を足せばよい。 |
|
【問題４】問題３は後回しにします。第137回の解答より、『a1+a2+･･･+ak=iを満たす組(a1,a2,･･･,ak)は、例えばi個のみかんをk人に配る場合数kHi(=k+i-1Ci) と同じ』ですから、 |
|
【問題３】問題４の配分を行う前に、3人に1個のみかんを与えておけばよいので、7個のみかんを3人に配るのと同じですから、 |
|
【問題５】x1〜x6の存在範囲を図示すると、 |
