1000円分の切手の買い方、Pythonで教えます

f:id:iGCN:20190610183813j:plain

さて

1000円分の切手を買ってきてとインターンの学生に指示したところ、1000円切手を1枚買ってきたというほっこりエピソードがTwitterで話題になっています。

ではインターン学生はどのように1000円分の切手を買ってくればよかったのでしょうか?

Pythonを使って答えてみようと思います。

日本の切手は19種類

この問題を考えるにあたっては、まず日本国内で入手できる切手の額面を知らなければなりません。

こちらのブログ記事によれば、1円切手から1000円切手まで全部で19種類の切手があるとのことです。

具体的には、額面別でいうと1, 2, 3, 5, 10, 20, 30, 50, 62, 82, 92, 100, 120, 140, 205, 280, 310, 500, 1000円となっています。

さらに62, 82, 92円切手については慶事用、62円切手については弔辞用の切手がありますが、今回は特段の指示がなかったので通常の普通切手を買うということにします。

いまだに現金払い?問題の応用

これら19種類の切手を組み合わせて1000円分買うという問題になります。

ここからは私のサブブログである、Pythonで解く数学パズルのこちらの記事を参考にして考えていきたいと思います。

これは1000円を両替するときの硬貨の組み合わせを問う問題です。コインの種類は切手に比べれば少ないのと、最大15枚までの組み合わせを問うています。

この問題に対する模範回答を改変してプログラムを組んでみました。

私が組んだPythonプログラムがこちら

import itertools

a = 0
stamps = [1, 2, 3, 5, 10, 20, 30, 50, 62, 82, 92, 100, 120, 140, 205, 280, 310, 500, 1000]
for n in range (1, 1001):
    for combi in itertools.combinations_with_replacement(stamps, n):
        if sum(combi) == 1000:
            print (combi)
            a += 1
print (a)

1000切手を1枚買うという考えから、最大は1円切手を1000枚買うまでの組み合わせを全て計算しようとしてみましたが、これだとエラーが出てしまって答えが出せませんでした。

range (1, 1001)の部分を書き換えて、少ない枚数の組み合わせから計算して行ってみたところ、結果は以下の通りでした。

切手の枚数 組合せの数
1枚 1通り
2枚 2通り
3枚 2通り
4枚 6通り
5枚 23通り
6枚 97通り
7枚 370通り
8枚 1272通り
9枚 3965通り
10枚 11169通り
11枚 28510通り
12枚 66701通り
13枚 144657通り
14枚 293569通り
15枚 561958通り

paizaのオンライン実行環境でコードを実行したのですが、途中から組合わせの数が指数関数的に増えてきて、9枚の組み合わせから先は計算ができなくなってしまいました。より良い環境がある方は、この先をぜひ計算して教えてください。

追記:Google Colaboratoryの環境で15枚の組み合わせまでは計算してみました。56万通り超えてるけど。

さいごに

「1000円分切手買ってきて」という指示は、指示として成立していないと思います。組合せの数が天文学的なので、指示されたインターンの学生はどうしたらよいか分からなくなってしまったと思います。

私なら1円切手を1000枚買っていくと思いますがね。

では