フロベニウスの硬貨交換問題:3か月でマスターする数学【2024/08/14】

ドイツのフロベニウスという人が考えた問題がある。

それが、硬貨交換問題。

「4円玉と7円玉で作ることのできない最大の金額は?」

この問題を不定方程式で表すと、

4x + 7y = k となるが、

求めるのは、作ることのできない最大の金額。

数字を7ずつ折り返し順番に並べて、

できるものにはバツ、できないものにはマルをつけていく。

まず、4と7は作ることができるのがすぐわかる。

そして、作ることができた金額の真下の数は、

7の倍数を足しているので、バツで消すことができる。

さらに、消した数字の右下の数は、

4の倍数を足しているので、バツで消すことができる。

また、4円玉でできる、8、16、24の真下も、

7の倍数を足しているので、消すことができる。

今回の数は42までだったが、これ以降の数字も、バツになる。

その結果、1,2,3,5,6,9,10,13,17 の数が残り、

答えは「17」となる。

この問題、答えを自動的に求める公式がある。

x円玉とy円玉で作ることのできない最大の金額は、

xy - x - y 円
(x,yは、1以外に共通の約数を持たない)

今回の場合は、4x7-4-7=17

これは、フロベニウス数と名付けられ、

この分野の重要な研究対象となっている。