1000円分の切手の購入には、何通りの手法があるか？

数学 趣味

https://twitter.com/ooki_kazuma/status/1137925359393943553
こんなツイートがバズっていた。

「1000円分の切手を購入して」と頼まれたとき、一体何通りの買い方があるのだろう。
さすがに手計算は厳しい。10円くらいなら頑張れるけど1000円は相当の努力を要する。
プログラマではないけど、なんとなく実装してみる。

考え方としては、動的計画法？を使うと良さそうだ。
例えば切手が1円と2円のものしかなければ、
5円を切手で買う場合、3円を切手買う通り数と4円を切手で買う通り数の合計が5円を切手で買う通り数になる。
それぞれに2円切手と1円切手を追加する手法があるからだ。

このあたりの数学的な話は、ちょうどAtCoderBeginnersContestのCで最近出たばかりだ。（これもTwitterで見ただけで、参加したわけではない）
atcoder.jp

#include <stdio.h>
#define N 1000
int main(void){
  double a[N+1]={};
  int stamp[19]={1,2,3,5,10,20,30,50,62,82,92,100,120,140,205,280,310,500,1000};

  a[0]=1;
  for(int i=1; i<=N; ++i){
    for(int j=0 ; j<=18; ++j){
      if(stamp[j] <= i){a[i]+=a[(i-stamp[j])];}
    }
  }
  printf("%\lf\n", a[N]);
}

という適当なコードを書いたら、
2018816696222833910656252468851793841738864262054617892302459180312970595153790345675412673676673112703307948339857624925883177447105511378331105500927787309118585058021154540560775964571577964892483432744215161103404706532767038310124338081271084872173277731084108619793301504

通りと出た。
doubleを使っているので多分これは精度が悪い。でも1.798...*10^308程度のdoubleの範囲を超えなかったのは幸い。おおよそ正しい値だろう。

 
安い金額に対しては同様のプログラムで厳密に求められる。
Nを変えていくと、1円から始まり

1(1円の場合), 2, 4, 7, 14, 26, 49, 93, 175, 332(10円の場合)通りの買い方があるらしい。10円でも332通り。

激しい指数関数的な増加である。


でも、厳密な解が知りたい。
ここでpythonを使ってみよう！
精度を高める手法があるらしい。

とはいっても私はpythonなんて使ってないので、decimalなんて環境も知らなければ配列の使い方さえ知らなかった。
検索しながら30分くらい格闘して以下のコードを作る。 

from decimal import *
getcontext().prec=1000

nums=[Decimal('1')]
stamps=[Decimal('1'),Decimal('2'),Decimal('3'),Decimal('5'),Decimal('10'),Decimal('20'),Decimal('30'),Decimal('50'),Decimal('62'),Decimal('82'),Decimal('92'),Decimal('100'),Decimal('120'),Decimal('140'),Decimal('205'),Decimal('280'),Decimal('310'),Decimal('500'),Decimal('1000')]

for i in range(1, 1001):
  nums.append(0)
  for j in range(0, 19):
  if stamps[j] <= i:
    nums[i] = nums[i]+nums[i-int(stamps[j])]
print(nums[1000])

2018816696222847406903248298783095971003454597950956950486814286870151769566638334351695889582461204439244633372769436724665312005396075530178629791204098410261766867285766690432361030106623128263952566362440060615017667935586334548238897367080748492851021980966669336418640390
とでた。

ちなみにgetcontext().prec=1000というのが精度である。10進で1000桁には行かないので適当な設定。


52bit（doubleの仮数部分の精度）は大体15〜16桁精度だ。
getcontext().prec=15にしてみると
2.01881669622321E+276
とでた。

C言語のdoubleでは
2.0188166962228339E+276だったので、まあ誤差でそんなものだろう。
2.01881669622321E+276←15桁精度
2.018816696222854E+276←16桁精度
2.0188166962228474069←1000桁精度


python初めて30分みたいな人が書いたプログラムなので自信がない。
1,2,3,5,10,20,30,50,62,82,92,100,120,140,205,280,310,500,1000円切手があった場合、1000円分の切手を買う方法は

2018816696222847406903248298783095971003454597950956950486814286870151769566638334351695889582461204439244633372769436724665312005396075530178629791204098410261766867285766690432361030106623128263952566362440060615017667935586334548238897367080748492851021980966669336418640390通りなのかな。

だれか、正しいか検証して欲しい。

2019年6月11日18:16追記
rubyは自動で桁数を増やしてくれると聞いたので実装した

nums = [1];
stamps = [1,2,3,5,10,20,30,50,62,82,92,100,120,140,205,280,310,500,1000];

for i in 1..1000 do
    nums.push(0)
    for j in 0..18 do
        if stamps[j] <= i then
            nums[i] = nums[i] + nums[i-stamps[j]];
        end
    end
end

print(nums[1000]);

同じ結果
2018816696222847406903248298783095971003454597950956950486814286870151769566638334351695889582461204439244633372769436724665312005396075530178629791204098410261766867285766690432361030106623128263952566362440060615017667935586334548238897367080748492851021980966669336418640390
を得た。

謝辞