平成１９年９月２３日
[流れ星]
第1９６回数学的な応募問題解答
＜解答募集期間：９月２日～９月２３日
［集金の方法］
皆さん、次のような両替の問題を考えました。よろしくお願いします。
問題１：５０ｎ円を５０円硬貨、１０円硬貨だけで集金する方法は何通りあるか。ｎで表せ。
問題２：１００ｎ円を、１００円硬貨、５０円硬貨、１０円硬貨だけで集金する方法は何通りあるか。ｎで表せ。
問題３：５００ｎ円を、５００円硬貨、１００円硬貨、５０円硬貨、１０円硬貨だけで集金する方法は何通りあるか。ｎで表せ。
以上の問題で、ｎは自然数を表す。ただし、青の字は９月３日に修正しました。
＜ヒント：解法が分からなかったら、ｎ＝１、２、３、・・・と実際に数えていき、漸化式を作ってください。＞
＜水の流れ：「新俳人澄朝」から、
「２００円を５０円硬貨、１０円硬貨に両替する」とき、持っている２００円は、１００円玉２枚と考えるのか？５０円硬貨４枚等とは考えないのか？」
「５０円を５０円硬貨、１０円硬貨に両替する」とき、５０円玉を５０円硬貨で両替するというのか、言わないのか？」という疑問があり、上のようにしました。ご迷惑をおかけしましたことを陳謝します。＞
ＮＯ１「uchinyan」09/02 14時13分受信 更新9/23
第１９６回数学的な応募問題
［硬貨の両替］
問題１：
50円硬貨を x 枚，10円硬貨を y 枚で両替するとすると，要するに，50n を 50x と 10y とに分解すればいいので，
50x + 10y = 50n
ただし，x, y は，x, y >= 0 の整数です。
式を簡単にして，
5x + y = 5n
y = 5n - 5x
x を 0, 1, 2, ..., n とすると，それぞれに対して y は一意に確定するので，n+1 通りになります。
問題２：
100円硬貨を x 枚，50円硬貨を y 枚，10円硬貨を z 枚で両替するとすると，x, y, z >= 0 の整数として，
100x + 50y + 10z = 100n
10x + 5y + z = 10n
z = 10n - (10x + 5y)
x, y に z >= 0 となるような 0 以上の整数を与えれば，z は一意に確定します。そこで，
0 <= 10x + 5y <= 10n
0 <= 2x + y <= 2n
となる 0 以上の整数の組 (x, y) の個数に等しくなります。これは，
0 <= y <= 2n - 2x
となる 0 以上の整数の組 (x, y) の個数なので，
x = 0, 1, 2, ..., n を与えれば，そのそれぞれの x の値に対して，
y = 0, 1, 2, ..., 2n - 2x (の 2n - 2x + 1 個)をとる
となります。そこで，個数の総数＝両替の仕方，は，
∑[x=0,n]{∑[y=0,2n-2x]{1}}
∑[x=0,n]{2n-2x+1}
= (2n+1) * (n+1) - 2 * n(n+1)/2
= (n+1)^2 通り
になります。
問題３：
500円硬貨を x 枚，100円硬貨を y 枚，50円硬貨を z 枚，10円硬貨を u 枚で両替するとすると，
x, y, z, u >= 0 の整数として，
500x + 100y + 50z + 10u = 500n
50x + 10y + 5z + u = 50n
u = 50n - (50x + 10y + z)
x, y, z に u >= 0 となるような 0 以上の整数を与えれば，u は一意に確定します。そこで，
0 <= 50x + 10y + 5z <= 50n
0 <= 10x + 2y + z <= 10n
となる 0 以上の整数の組 (x, y, z) の個数に等しくなります。これは，
0 <= z <= 10n - 10x - 2y
となる 0 以上の整数の組 (x, y, z) の個数で，0 以上の整数の組 (x, y) を与えれば，z は，
z = 0, 1, ..., 10n - 10x - 2y (の 10n - 10x - 2y + 1 個)をとる
と分かります。このとき，x, y は，10n - 10x -
2y >= 0 となる 0 以上の整数なので，
0 <= y <= 5n - 5x
となっていなければなりません。これは，
x = 0, 1, 2, ..., n を与えれば，そのそれぞれの x の値に対して，
y = 0, 1, 2, ..., 5n - 5x をとる
となります。そこで，個数の総数＝両替の仕方，は，
∑[x=0,n]{∑[y=0,5n-5x]{∑[z=0,10n-10x-2y]{1}}}
= ∑[x=0,n]{∑[y=0,5n-5x]{10n-10x-2y+1}}
= ∑[x=0,n]{(10n-10x+1) * (5n-5x+1) - 2 *
(5n-5x)(5n-5x+1)/2}
= ∑[x=0,n]{(5n-5x+1) * (5n-5x+1)}
= ∑[x=0,n]{(5n+1)^2 - 10 * (5n+1) * x + 25 * x^2}
= (5n+1)^2 * (n+1) - 10 * (5n+1) * n(n+1)/2 + 25 * n(n+1)(2n+1)/6
= (n+1)/6 * {6 * (5n+1)^2 - 30 * n(5n+1) + 25 * n(2n+1)}
= (n+1)/6 * {6 * (5n+1)(5n+1 - 5n) + 25 * n(2n+1)}
= (n+1)/6 * (50 * n^2 + 55 * n + 6)
= (n+1)(50n^2 + 55n + 6)/6 通り
になります。
(感想)
問題２：の答えがきれいになったので，ひょっとしたら，と期待しましたが，
問題３：の結果を見る限り，そううまくはいかないようです。
なお，さすがに，5円硬貨，1円硬貨での両替はなしですかねぇ～ (^^;
＜水の流れ：9月2日のときの問題文は硬貨の両替でした。ご迷惑をおかけしています＞
ＮＯ２「ｽﾓｰｸﾏﾝ」 09/04 11時13分受信
「ｽﾓｰｸﾏﾝ」 09/05 01時30分受信
更新9/23
１．50n=50a+10b
n>=1
a=0,1,2,・・・,n
に対応して1：1で、bの値は決まる。
つまり、n+1通り。
２．100n=100a+50b+10c
a=0,1,2,・・・,n
a=0 のとき、100n=50*2n=50b+10c から、2n+1通り。
a=1 のとき、100(n-1)=50*2(n-1)=50b+10c から、2(n-1)+1=2n-1
a=2 のとき、100(n-2)=50*2(n-2)=50b+10c から、2(n-2)+1=2n-3
・
・
・
a=n のとき、100*0=50*0=50b+10c から、2(n-n)+1=2n-(2n-1)
つまり、2n*(n+1)+1-Σ(奇数：1～2n-1):k=2n(n+1)-2n*n/2
=2n^2+2n+1-n^2
=n^2+2n+1
=(n+1)^2・・・答え
３．500n=500a+100b+50c+10d
a=0 のとき、100*5n=100b+50c+10d・・・(5n+1)^2
a=1 のとき、100*5(n-1)=100b+50c+10d・・・(5n-5+1)^2=(5n-4)^2
a=2 のとき、100*5(n-2)=100b+50c+10d・・・(5n-10+1)^2=(5n-9)^2
・
・
・
a=n のとき、100*5(n-n)=100b+50c+10d・・・(5n-5n+1)^2
(5n-(5k-1))^2=25n^2-10(5k-1)n+(5k-1)^2
合計=25n^2*(n+1)-10n*Σ(0～n):(5k-1)+25Σ(0～n):k^2-10Σ(0～n):k+(n+1)
=25(n^3+n^2)-10n*(5n(n+1)/2-(n+1))+25*n(n+1)(2n+1)/6-10*n(n+1)/2+(n+1)
=25(n^3+n^2)-25n^2(n+1)+11n(n+1)+25(2n^3+3n^2+n)/6-5n(n+1)
=(150(n^3+n^2)-150(n^3+n^2)+36n(n+1)+25(2n^3+3n^2+n))/6
=(50n^3+111n^2+61n)/6
=n(50n^2+111n+61)/6
=n(50n+1)(n+61)/6・・・答え
n=0,+-1,+-2,+-3 でも整数になるからよさそうかな。。。^^;
*(k+1)^3-k^3=3k^2+3k+1
(n+1)^3-1=3Σk^2+3n(n+1)/2+n
3Σk^2=(2(n^3+3n^2+3n+1)-3n^2-3n-2n-2)/2
=n(2n^2+3n+1)/2
=n(n+1)(2n+1)/2
Σk^2=n(n+1)(2n+1)/6
＜水の流れ：問題３の答えがこちらと合っていないのですが・・・＞
ＮＯ３「新俳人澄朝」9/23 13時35分受信 更新9/23
ＮＯ４「kashiwagi｣09/16 08時37分受信 更新9/23
196回問題
題意に従い、ｎの値を変化させ表を作成して考えました。表は添付致しました。
問1.表から明らかなように 
となる。
問2.表から明らかなように 
となる。
問3.これは表から明らかとはいかず、
の時500円硬貨が0枚の場合36通り、500円硬貨が1枚の時1通り、即ち、
同様にして
の時時500円硬貨が0枚の場合121通り、500円硬貨が1枚の時36通り、500円硬貨が2枚の時1通り即ち、
これより次のように推定できる。
＝
＝
＝
となる。
ＮＯ５「Toru」 09/18 11時51分受信 更新9/23
問題１ ５０円硬貨がn枚～０枚で (n+1) 通り
問題２ １００円硬貨が (n-k) 枚（k=0～n）の時 残りの(50x2k) 円を50円硬貨
と10円硬貨だけで集金すると考えて問題１より(2k+1) 通り (k=0の時もok)
よって全体でΣ(k=0～n)(2k+1)=(n+1)^2
(通り)
問題３ ５００円硬貨が (n-k) 枚（k=0～n）の時 残りの(100x5k)円を１００円硬
貨、５０円硬貨、１０円硬貨だけで集金すると考えて、問題２より (5k+1)^2 通り。
(k=0の時もok)
よって全体で
Σ(k=0～n)(5k+1)^2=Σ(25k^2+10k+1)
=25n(n+1)(2n+1)/6 + 5n(n+1) +(n+1)=(n+1)(50n^2+55n+6)/6 （通り）
漸化式にしませんでしたが、内容的には同じようなことかと思っています。
両替えという言葉が問題となったようで、あらためて問題をつくる側の苦労を感じました。私なぞは最初から、
５０n円を１０円玉と５０円玉で構成すると考えて、問題を感じもしませんでしたが、そう言われればそうですね。
個人的には、回答者の方でも出題者の意図を察するような、あうんの呼吸があってもよいような気がしてはい
ます。
ＮＯ６「ぐーてん」09/13 17時22分受信 更新9/23
出張続きでしばらくさぼっていましたが、一段落したので再開させていただこうと思います。よろしくお願いします。
なにしろ、私の実力では解くのに相当時間がかかっていますので^^;
(3)の図は、3D-CADを駆使して描いてみました。3D-CADの勉強にもなり、一石二鳥でした。
（１）使用できる50円玉の枚数は，0～n枚のn+1通り．それぞれの場合において，残額全てを10円玉で集金すればよいので，求める方法の数はn+1通り．
（２）
使用する10円玉，50円玉，100円玉の枚数をi，j，k枚（i，j，kは0または自然数）とおくと，j，kは0≦k≦n，0≦j≦2n-2kを満たす任意の値をとり，それぞれの場合に残額を10円玉で集金すればよい（i=10n-10k-5j）．
従って求める方法の数は，図（n=4の場合）に示すような領域に含まれる格子点の数に等しい．斜線で示すような合同でかつ同じパターンで格子点を含む領域を考えて求めると，
通り．
（３）
使用する10円玉，50円玉，100円玉，500円玉の枚数をi，j，k，l枚（i，j，k，lは0または自然数）とおくと，j，k，lは0≦l≦n，0≦k≦5n-5l，0≦j≦10n-10l-2kを満たす任意の値をとり，それぞれの場合に残額を10円玉で集金すればよい（i=50n-50l-10k-5j）．
従って求める方法の数は，図（n=4の場合）に示すような領域に含まれる格子点の数に等しく，
ＮＯ７「bear56」 09/17 13時27分受信
「bear56」 09/18 00時05分受信 更新9/23
＜コメント：勝手に付けた仮題は冗長な気がするし，問題３のｎの式は変な感じがしますが，
どうするのが美しいのか，よくわかりません．数列の和の公式を使いました．＞
集金の方法
仮題 まずは，１０ｎ円を１０円硬貨だけで集金する方法は何通りあるかを考える．
１０ｎ円を集金する組み合わせの数をＰ１０（ｎ）とし，
１０円硬貨の個数をａとする．
１０ｎ＝１０ａ
ａ＝ｎ
１０円硬貨の個数ａは，全てのｎについてａが１通りづつ定まり，
その組み合せＰ１０（ｎ）は， Ｐ１０（ｎ）＝∑１＝ｎ．
∑の束縛変数はｋとし，ｋは１≦ｋ≦ｎの自然数．（以下，同様）
問題１ ５０ｎ円を集金する組み合わせの数をＰ５０（ｎ）とし，
１０ｍ円を集金する組み合わせの数を先Ｐ１０（ｍ）とし（仮題），
１０円硬貨の個数をａ，５０円硬貨の個数をｂとする．
５０ｎ＝１０ａ＋５０ｂ
（ミス）ここで，０≦ａ≦ｎ，０≦ｂ≦ｎである．
（修正）ここで，０≦ａ≦５ｎ，０≦ｂ≦ｎである．
ｂ＝ｎの場合は，ａ＝０の１通りである．
ｂ＜ｎの場合は，仮題により，
５ｎ＝ｍ＋５ｂ
ｍ＝５（ｎ－ｂ）
５０円硬貨の個数ｂに対して，
残りの１０円硬貨の個数ａの組み合せは，
仮題により，ｍ＝５（ｎ－ｂ）として求められ，
ｂ＜ｎについて，Ｐ１０（ｍ）が定まる．
全ての組み合せＰ５０（ｎ）は，ｋ＝ｎ－ｂとして，
Ｐ５０（ｎ）＝∑Ｐ１０（５ｋ）＋１
＝∑１＋１
＝ｎ＋１．
したがって，
ｎ＋１通り．
問題２
１００ｎ円を集金する組み合わせの数をＰ１００（ｎ）とし，
５０ｍ円を集金する組み合わせの数をＰ５０（ｍ）とし（問題１），
１０円硬貨の個数をａ，５０円硬貨の個数をｂ，１００円硬貨の個数をｃとする．
１００ｎ＝１０ａ＋５０ｂ＋１００ｃ
（ミス）ここで，０≦ａ≦ｎ，０≦ｂ≦ｎ，０≦ｃ≦ｎである．
（修正）ここで，０≦ａ≦１０ｎ，０≦ｂ≦２ｎ，０≦ｃ≦ｎである．
ｃ＝ｎの場合は，ａ＝０，ｂ＝０の１通りである．
ｃ＜ｎの場合は，問題１により，
１００ｎ＝５０ｍ＋１００ｃ
ｍ＝２（ｎ－ｃ）
１００円硬貨の個数ｃに対して，
残りの１０円硬貨の個数ａ，５０円硬貨の個数ｂの組み合せは，
問題１により，ｍ＝２（ｎ－ｃ）として求められ，
ｃ＜ｎについて，Ｐ５０（ｍ）が定まる．
全ての組み合せＰ１００（ｎ）は，ｋ＝ｎ－ｃとして，
Ｐ１００（ｎ）＝∑Ｐ５０（２ｋ）＋１
＝∑（２ｋ＋１）＋１
＝２∑ｋ＋∑１＋１
＝２［ｎ（ｎ＋１）／２］＋ｎ＋１
＝（ｎ＋１）（ｎ＋１）
＝（ｎ＋１）＾２
したがって， （ｎ＋１）＾２通り．
問題３
５００ｎ円を集金する組み合わせの数をＰ５００（ｎ）とし，
１００ｍ円を集金する組み合わせの数をＰ１００（ｍ）とし（問題２），
１０円硬貨の個数をａ，５０円硬貨の個数をｂ，１００円硬貨の個数を，５００円硬貨の個数をｄ とする．
５００ｎ＝１０ａ＋５０ｂ＋１００ｃ＋５００ｄ
（ミス）ここで，０≦ａ≦ｎ，０≦ｂ≦ｎ，０≦ｃ≦ｎ，０≦ｄ≦ｎである．
（修正）ここで，０≦ａ≦５０ｎ，０≦ｂ≦１０ｎ，０≦ｃ≦５ｎ，０≦ｄ≦ｎである．
ｄ＝ｎの場合は，ａ＝０，ｂ＝０，ｃ＝０の１通りである．
ｄ＜ｎの場合は，問題２により，
５００ｎ＝１００ｍ＋５００ｄ
ｍ＝５（ｎ－ｄ）
５００円硬貨の個数ｄに対して，
残りの１０円硬貨の個数ａ，５０円硬貨の個数ｂ，１００円硬貨の個数ｃの組み合せは，
問題２により，ｍ＝５（ｎ－ｄ）として求められ，
ｄ＜ｎについて，Ｐ１００（ｍ）が定まる．
全ての組み合せＰ５００（ｎ）は，ｋ＝ｎ－ｄとして，
Ｐ５００（ｎ）＝∑［Ｐ１００（５ｋ）］＋１
＝∑［（５ｋ＋１）＾２］＋１
＝２５∑（ｋ＾２）＋１０∑ｋ＋∑１＋１
＝２５［ｎ（ｎ＋１）（２ｎ＋１）／６］＋１０［ｎ（ｎ＋１）／２］＋ｎ＋１
＝［２５ｎ（ｎ＋１）（２ｎ＋１）＋３０ｎ（ｎ＋１）＋６（ｎ＋１）］／６
＝（ｎ＋１）［２５ｎ（２ｎ＋１）＋３０ｎ＋６］／６
＝（ｎ＋１）［５０ｎ＾２＋５５ｎ＋５＋１］／６
＝（ｎ＋１）［５（ｎ＋１）（１０ｎ＋１）＋１］／６
したがって， （ｎ＋１）［５（ｎ＋１）（１０ｎ＋１）＋１］／６通り．
ＮＯ８「kasama」
09/19 22時41分受信
「kasama」 09/21 00時58分受信 更新9/23
|
問題１ 50円硬貨で集金して、残りを10円硬貨で集金すると考えます。50円硬貨の集金は0円,50円,100円,…,50n円です。よって、場合数はan=n+1通りです。 |
|
|
|
問題２ 100円、50円、10円硬貨だけで100n円を集金する場合数をbnとします。100円硬貨を使う場合とそうでない場合に分けて考えます。100円硬貨を使わないときは、50円、10円硬貨だけで100n=50×2n円を集金する場合と同じだからa2n通りです。よって、漸化式は、 |
|
|
|
問題３ 500円、100円、50円、10円硬貨だけで500n円を集金する場合数をcnとします。上と同様にして、500円硬貨を使わないときは、100円、50円、10円硬貨だけで500n=100×5n円を集金する場合と同じだから、漸化式は、 |