NO.1849 両皿天秤のオモリ(2) 2010.4.24. 夜ふかしのつらいおじさん
エレガントな解答はないように思います。
両皿天秤のオモリの問題ですが、お金の支払いの問題として考えます。
その方が分かりやすい気がします。
まず、基本的なことを見ておきます。
● おつりをもらわないで支払いをするなら、｛１，２，４，８，１６｝円硬貨を使います。
２進法で数を表すことを考えれば理解できます。
１円から、１＋２＋４＋８＋１６＝３１円までもれなくだぶりなく支払えます。
１枚の硬貨は｛使う，使わない｝の２通りです。
だから、２5＝３２より、０円のときを除いて３１通りです。
１円を支払うのに、１円硬貨を使います。
２円を支払うのに、２円硬貨を使います。
３円を支払うのに、１円硬貨と２円硬貨を使います。
４円を支払うのに、４円硬貨を使います。
・・・
硬貨の種類を、金額が小さい順に増やすことを考えます。
持っている硬貨を全部使って支払えない最小の金額の硬貨があれば良いことになります。
● おつりをもらうことができるのならば、｛１，３，９，２７，８１｝円硬貨を使います。
買い物をする人とお店にこの金額の硬貨があれば、12１円までもれなくだぶりなく金額の支払いができます。
仕組みを、｛１，３，９｝の簡単な場合で説明します。
買い物をする人とお店にこの金額の硬貨があれば、１３円までもれなくだぶりなく金額の支払いができます。
３の倍数は次のように表せます。
「＋」は支払い、「－」はおつりと考えます。
３＝３， ６＝９－３， ９＝９， １２＝９＋３
自然数は、｛３ｎ，３ｎ＋１，３ｎ－１｝のどれかの形をしています。
上のように、１円以外の硬貨ですべての３の倍数の金額を表すことができます。
１円硬貨を支払えば３ｎ＋１円、１円硬貨でおつりをもらえば３ｎ－１円となるからです。
１枚の硬貨は｛使う，使わない，おつりでもらう｝の３通りがあります。
３3＝２７です。
｛支払額＞おつりの金額｝、｛０｝、｛支払額＜おつりの金額｝の場合があるので、
支払える金額は、（２７－１）／２＝１３通りあります。
１円を支払うのに、１円硬貨を使います。
２円を支払うのに、３円硬貨を使い、おつりを１円もらいます。（３＝２＋１）
３円を支払うのに、３円硬貨を使います。
４円を支払うのに、３円硬貨と１円硬貨を使います。
５円を支払うのに、９円硬貨を使い、おつりを４円もらいます。（９＝５＋３＋１）
・・・
硬貨の種類を、金額が小さい順に増やすことを考えます。
持っている硬貨を全部使って支払えない最小の金額とそれまでの硬貨の金額を全部足した額の硬貨があればよいことになります。
● ５枚の硬貨を使う場合、最大で１２１通りの支払いが可能です。
１０円硬貨が混ざると、上の例からはずれます。
１０円硬貨が混ざると、考える糸口として次のことが考えられます。
ｎ円の金額を作れたとき、次のように２７通りの金額をつくることができます。
上の×の部分を埋めて、連続した金額をつくるとき、例えば次のような様子になっています。
１円硬貨を使う場合、２つ分の金額が重なります。
２円硬貨を使う場合、うまく互い違いになっています。
このように、２円硬貨を使う方が効率が良いように思います。
この差が多分２円硬貨を使う理由の１つでしょう。
このように試行錯誤していくしかないと思います。
以下にいくつかの硬貨の組合せの例を書いておきます。
