たまたま持っている硬貨を利用している。
そこで、自動販売機が受け付けている10円、50円、100円、500円硬貨で、1000円の品物を
販売機で購入するとした場合、販売機は全部で何通りの硬貨の組合せを受け付けることに
なるのか？
また、5円玉も販売機が受け付けるようにしたとすれば、その硬貨の組合せはどれほどに
なるものか？
想像するのも恐ろしいが、1円玉も受け付けるならどうなってしまう？
ただし、販売機は硬貨は何個でも受け付けるものとする。
Dengan kesaktian Indukmu さんからのコメントです。（令和６年５月１日付け）
ひょっとして、10円玉までで、158通りでしょうか？
((x^50)^2+(x^50)+1)*((x^10)^10+(x^10)^9+(x^10)^8+(x^10)^7+(x^10)^6+(x^10)^5+(x^10)^4
+(x^10)^3+(x^10)^2+(x^10)^1+1)*((x^5)^20+(x^5)^19+(x^5)^18+(x^5)^17+(x^5)^16+(x^5)^15
+(x^5)^14+(x^5)^13+(x^5)^12+(x^5)^11+(x^5)^10+(x^5)^9+(x^5)^8+(x^5)^7+(x^5)^6+(x^5)^5
+(x^5)^4+(x^5)^3+(x^5)^2+(x^5)^1+1)*((x)^100+(x)^95+(x)^90+(x)^85+(x)^80+(x)^75+(x)^70
+(x)^65+(x)^60+(x)^55+(x)^50+(x)^45+(x)^40+(x)^35+(x)^30+(x)^25+(x)^20+(x)^15+(x)^10
+(x)^5+1)
を展開して、x^100 の項の係数をみました。
本当は次の式を展開したかったのですが、オンライン展開サービスが受け付けてくれませ
んでした。
((A*x^50)^2+(A*x^50)+1)*((B*x^10)^10+(B*x^10)^9+(B*x^10)^8+(B*x^10)^7+(B*x^10)^6
+(B*x^10)^5+(B*x^10)^4+(B*x^10)^3+(B*x^10)^2+(B*x^10)^1+1)*((C*x^5)^20+(C*x^5)^19
+(C*x^5)^18+(C*x^5)^17+(C*x^5)^16+(C*x^5)^15+(C*x^5)^14+(C*x^5)^13+(C*x^5)^12
+(C*x^5)^11+(C*x^5)^10+(C*x^5)^9+(C*x^5)^8+(C*x^5)^7+(C*x^5)^6+(C*x^5)^5+(C*x^5)^4
+(C*x^5)^3+(C*x^5)^2+(C*x^5)^1+1)*((D*x)^100+(D*x)^95+(D*x)^90+(D*x)^85+(D*x)^80
+(D*x)^75+(D*x)^70+(D*x)^65+(D*x)^60+(D*x)^55+(D*x)^50+(D*x)^45+(D*x)^40+(D*x)^35
+(D*x)^30+(D*x)^25+(D*x)^20+(D*x)^15+(D*x)^10+(D*x)^5+1)
10円＝1ギルドとして、100ギルドの商品を、1ギルド、5ギルド、10ギルド、50ギルドの硬貨で
支払いたいと考えます。
このとき、1ギルド硬貨の枚数は明らかに5の倍数なので、そうした縛りをつけます。
(D*x) は1ギルド硬貨のシンボルです。この項の肩にのっかる指数は、1ギルド硬貨で支払
う価格を表します。上の式では0ギルドから100ギルドまで5ギルド単位の全ての可能性を列
挙しています。
(C*x^5)は５ギルド硬貨のシンボルです。0枚から20枚まで、肩の指数でもって１枚づつの刻
みで列挙します。
同様に、(B*x^10)及びに(A*x^50)は、それぞれ、10ギルド硬貨、50ギルド硬貨のシンボルで
す。式での意味はここまでの扱いに準拠します。
さきほどの式は、それぞれの硬貨の枚数の上限およびに刻みに制限を付与した上で、支
払える金額の全てのパターンを自動的に(展開をしてくれるサイトを利用してですが)求める
ものです。
x の指数が100のものの全てのバリエーションが求めるものなのですが．．．。まじめに展開
できれば、100ギルドの支払い方が各係数をみることでわかるはずです。
展開してくれるサイトがみつからなかったので、AからDまでに1を代入して、バリエーション
の組み合わせの数のみ求めることとしました。
らすかるさんからのコメントです。（令和６年５月２日付け）
（一つ目）
10円硬貨で10n円を表す方法は1通り → 50n円を表す方法も1通り
10円硬貨と50円硬貨で50n円を表す方法は、Σ[k=0〜n]1=n+1通り
→ 100n円を表す方法は2n+1通り
10円硬貨と50円硬貨と100円硬貨で100n円を表す方法は、Σ[k=0〜n]2k+1=(n+1)^2通り
→ 500n円を表す方法は(5n+1)^2通り
10円硬貨と50円硬貨と100円硬貨と500円硬貨で500n円を表す方法は、
Σ[k=0〜n](5k+1)^2=(n+1)(50n^2+55n+6)/6通り
よって、1000円を表す方法は、n=2 を代入して、3×316÷6=158通り
（二つ目）
5円硬貨で5n円を表す方法は1通り → 10n円を表す方法も1通り
5円硬貨と10円硬貨で10n円を表す方法は、Σ[k=0〜n]1=n+1通り
→ 50n円を表す方法は5n+1通り
5円硬貨と10円硬貨と50円硬貨で50n円を表す方法は、Σ[k=0〜n]5k+1=(n+1)(5n+2)/2通り
→ 100n円を表す方法は(2n+1){5(2n)+2}/2=(2n+1)(5n+1)通り
5円硬貨と10円硬貨と50円硬貨と100円硬貨で100n円を表す方法は、
Σ[k=0〜n](2k+1)(5k+1)=(n+1)(20n^2+31n+6)/6通り
→ 500n円を表す方法は(5n+1){20(5n)^2+31(5n)+6}/6=(5n+1)(500n^2+155n+6)/6通り
5円硬貨と10円硬貨と50円硬貨と100円硬貨と500円硬貨で500n円を表す方法は
Σ[k=0〜n](5k+1)(500k^2+155k+6)/6=(n+1)(625n^3+1050n^2+305n+6)/6通り
よって、1000円を表す方法は、n=2 を代入して、3×9816÷6=4908通り
（三つ目）
1円硬貨でn円を表す方法は1通り → 5n円を表す方法も1通り
1円硬貨と5円硬貨で5n円を表す方法は、Σ[k=0〜n]1=n+1通り
→ 10n円を表す方法は2n+1通り
1円硬貨と5円硬貨と10円硬貨で10n円を表す方法は、Σ[k=0〜n]2k+1=(n+1)^2通り
→ 50n円を表す方法は(5n+1)^2通り
1円硬貨と5円硬貨と10円硬貨と50円硬貨で50n円を表す方法は、
Σ[k=0〜n](5k+1)^2=(n+1)(50n^2+55n+6)/6通り
→ 100n円を表す方法は(2n+1){50(2n)^2+55(2n)+6}/6=(2n+1)(100n^2+55n+3)/3通り
1円硬貨と5円硬貨と10円硬貨と50円硬貨と100円硬貨で100n円を表す方法は、
Σ[k=0〜n](2k+1)(100k^2+55k+3)/3=(n+1)(100n^3+240n^2+131n+6)/6通り
→ 500n円を表す方法は(5n+1){100(5n)^3+240(5n)^2+131(5n)+6}/6
= (5n+1)(12500n^3+6000n^2+655n+6)/6通り
1円硬貨と5円硬貨と10円硬貨と50円硬貨と100円硬貨と500円硬貨で500n円を表す方法は
Σ[k=0〜n](5k+1)(12500k^3+6000k^2+655k+6)/6
= (n+1)(12500n^4+29375n^3+15800n^2-195n+6)/6通り
よって、1000円を表す方法は、n=2 を代入して、3×497816÷6=248908通り
ＧＡＩ さんからのコメントです。（令和６年５月１８日付け）
自動販売機での金種の投入方法で、
[500,100,50,10]円硬貨で1000円を支払う方法が158通り
[500,100,50,10,5]円硬貨では4908通り
[500,100,50,10,5,1]円硬貨では248908通り
が可能であることを見つけて貰っていたんですが、これをプログラムを使って求められない
かとRubyのソフトを用いて、
@cnt = 0
def change(target, coins, usable)
coin = coins.shift
if coins.size == 0 then
@cnt += 1 if target / coin <= usable
else
(0..target/coin).each{|i|
change(target - coin * i, coins.clone, usable - i)
}
end
end
change(1000, [500, 100, 50, 10], 100)
puts @cnt
から、158が入手でき
change(1000, [500, 100, 50, 10, 5], 200)
puts @cnt
から、4908が入手でき
change(1000, [500, 100, 50, 10, 5, 1], 1000)
puts @cnt
から、248908が計算できました。
そこで、[6, 4, 3, 2]で12を重複を許して支払おうとするとき、
change(12, [6, 4, 3, 2], 6)
で求まるはずだと実行すると、16 を返してきた。
明らかに、
6+6 、6+4+2 、6+3+3 、6+2+2+2 、4+4+4 、4+4+2+2 、4+3+3+2 、4+2+2+2+2 、3+3+3+3
3+3+2+2+2 、2+2+2+2+2+2
の11通りしかないので、上３つが正確に返すのに対し、なぜこれが誤った結果を返してくる
のか原因が分かりません。
プログラムの作り方は見よう見まねでやっているので詳しいことが分かりません。詳しい方
教えて下さい。
Dengan kesaktian Indukmu さんからのコメントです。（令和６年５月１８日付け）
[6, 4, 3, 1]で12を重複を許して支払おうとするときに、16通りになりますね。偶然？
らすかるさんからのコメントです。（令和６年５月１８日付け）
1000,[500,100,50,10],100 のようなケースでは、500と100と50をいくつずつ使っても、必ず残
りが10で割り切れますので、（つまり、最小以外の数(500,100,50)がすべての最小の数(10)で
割り切れる）
if target / coin <= usable
で問題が起こりませんが、12,[6,4,3,2],6 のように、最小の 2 で割り切れない数があると、
target が 2 で割り切れない場合でも
@cnt += 1
が実行されてしまうと思います。つまり、3 が奇数個使われて、最後に target が奇数になる
6+3+2
4+4+3
4+3+2+2
3+2+2+2+2
3+3+3+2
の5個（すべて1不足）が余計に数えられてしまっているのでしょう。
「if target / coin <= usable」
を
「if target が coin で割り切れ、かつ、target / coin <= usable」
に修正すれば正しく動くと思います。（Rubyの文法を知りませんので言葉で書きました）
Dengan kesaktian Indukmu さんからのコメントです。（令和６年５月１８日付け）
らすかるさんの仰る通りなのでしたか。
((x^6)^2+(x^6)+1)*((x^4)^3+(x^4)^2+(x^4)^1+1)*((x^3)^4+(x^3)^3+(x^3)^2+(x^3)^1+1)
*((x^2)^6+(x^2)^5+(x^2)^4+(x^2)^3+(x^2)^2+(x^2)^1+1)
を展開して x^11 の項の係数が 5 だとチラと頭をよぎったのですが、《targetが奇数》となる
ことをプログラムから読み取れませんでした。
以下、工事中！
