2021.09.22

硬貨でちょうど払えない金額を考える「フロベニウスの問題」とは?

新幹線の座席から硬貨の組み合わせまで
横山 明日希 プロフィール

「XY-X-Yが作れない」ことの証明

いま、

nX+mY=XY-X-Y(n,mは0以上の整数)

が成立すると仮定すると、式変形により

Y(m+1)=X(Y-1-n)

となりますが、ここで右辺はXの倍数であることになり、YはXと互いに素なのでm+1がXの倍数となります。また、Y-1-nはYの倍数となります。Y-1-nがYの倍数ということは、ここからYを引いて(-1)をかけた数1+nもYの倍数ということになります。nとmは正の数という条件も踏まえると、m+1はX以上の数、1+nはY以上の数といえます。つまり、m≧X-1、n≧Y-1です。これを先ほどの仮定した式の左辺に代入すると、

nX+mY≧(Y-1)X+(X-1)Y=2XY-X-Y

となり、先ほど仮定した式とは異なる結果を示す式となってしまい、矛盾します。よって最初の仮定の式が成立しないことが示されるため、XY-X-Yは作ることができないことがわかるのです。

後半の主張、「XY-X-Y+1以上は必ず作れる」についてはさらに踏み込んだ証明が必要になります。ここでは割愛しますが、このように「ある要素を組み合わせて数を作るとき、作ることができない数がいくつか?」という問題を数学的に捉えることが可能です。

このフロベニウスの硬貨問題について、コインの種類がもう1つ増えるだけで、答えを導出することが急に難しくなることが知られています。「互いに素である3つ以上の数において作ることができない最大の数」を求める公式は存在せず、ある程度の目安となる値を導出することができるまでしかまだ解明されていません。

フロベニウスの硬貨問題ですが、身近な素材なので自由研究の題材として…と言いたいところですが、ちょっと話題を広げると途端にとてつもない時間がかかる問題に変わります。ですが一見こういった単純そうに見える問題にも、手を伸ばせばまだ未解決な問題が眠っているのが、数学の1つの魅力だとも思えるのです。

関連記事