セルフレジのお釣りの小銭は必ず15枚以下になる

2022-05-08

キャッシュレスが増えてきていますが、現金払いもまだまだ健在です。そんな中、最近はセルフレジの導入が増えてきました。近くのスーパーもセルフレジを導入しており、支払い時に小銭を数えながらふと「セルフレジで小銭を毎回全投入すればある一定枚数以内に必ず収まるのではないかと」思い、計算をしてみました。

結論からいうとセルフレジが最小化枚数で小銭を返してくることを仮定すれば15枚以内には必ず収まります。
※ここで言う最小化枚数とは、例えば500円の場合は100円×5枚ではなく、500円×1枚で返してくるという意味です。

1000円以上はお札になるため、お釣りとして返ってくる小銭の最大値は999円となります。999円を分解すると500円×1枚、100円×4枚、50円×1枚、10円×4枚、5円×1枚、1円×4枚の15枚となります。

なんとなく理論としてはあっていると思っているのですが、証明が必要だと考え以下のプログラムを作成しました。プログラムでは1~999の値を各小銭の大きいから割っていくことでお釣りの最小枚数を求めています。

coin_nums = []
for change in range(1,1000):
    coin_num = 0
    coins = [500,100,50,10,5,1]
    for coin in coins:
        coin_num += change // coin
        change = change % coin
        if change == 0:
            break
    coin_nums.append(coin_num)
max(coin_nums)

こちらのプログラムですが、枚数の最大値max(coin_nums) = 15と算出されます。したがって999円以内のお釣りの最大枚数は15枚ということが証明できました。つまり、セルフレジで全小銭(初期値=999円)を投入した場合に必ず15枚以下になります。

15枚であればどのセルフレジでも許容範囲だと思います。よく、最大20枚 or 30枚までという記載が有るため、なかなか全額投入にチャレンジすることができませんでした。しかし、プログラムではあるものの最大枚数が証明できたため、セルフレジで支払う場合はとりあえず小銭を全額投入することで精算時間の短縮を図りたいと思います。

※注意
両替目的の大量の小銭投入はやめましょう。

※追記 2022/04/23

Twitterでこちらの投稿をしたところ@SUPIPI00様よりスマートなご回答をいただけましたので追記をさせていただきました。

こういう考えがぱっと浮かんで言葉にできるというのは憧れます🤩
なんとなく、成り立ちそうだと思っていても言葉にするのって難しい、、、