ドイツのフロベニウスという人が考えた問題がある。
それが、硬貨交換問題。
「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
これは、フロベニウス数と名付けられ、
この分野の重要な研究対象となっている。