日常の疑問
日常よく自動販売機なるものを利用しているが
客は決まった金種を入れる訳ではなく、たまたま持っている
硬貨を利用している。
そこで自動販売機が受け付けている10円,50円,100円,500円硬貨で
1000円の品物を販売機で購入するとした場合、販売機は全部で
何通りの硬貨の組合せを受け付けることになるのか？
また5円玉も販売機が受け付けるようにしたとすれば、その硬貨の
組合せはどれほどになるものか？
想像するのも恐ろしいが1円玉も受け付けるならどうなってしまう？
ただし販売機は硬貨は何個でも受け付けるものとする。
ひょっとして
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通り
