フロベニウスの硬貨交換問題とは？わかりやすく解説

2ペンスと5ペンスのコインだけでは、3ペンスを作ることはできないが、4ペンス以上は全て作ることができる。

フロベニウスの硬貨交換問題（フロベニウスのこうかこうかんもんだい）とは、指定された種類の硬貨だけではぴったり払えない最大の金額を求める数学の問題である^[1]。フロベニウスの問題、シルベスターの切手問題とも呼ばれる。数学者フェルディナント・ゲオルク・フロベニウスに因んで名付けられた。例えば、3円と5円の硬貨だけでは作れない最大の金額は7円である。コインの種類の組み合わせに対するこの問題の解はフロベニウス数と呼ばれる。フロベニウス数が存在するのは、硬貨の額面が互いに素のときに限られる。

硬貨が $a$ 円と $b$ 円の2種類だけの場合は、フロベニウス数の公式が存在し、 $ab - a - b (= (a - 1)(b - 1) - 1)$ である。硬貨が3種類以上の場合の公式は未解決問題である。しかし、任意の種類の硬貨に対して、（硬貨の種類の数の「対数」に対して）多項式時間でフロベニウス数を計算するアルゴリズムが存在する^[2]。硬貨の種類に対して多項式時間で解けるアルゴリズムは見つかっておらず、硬貨の種類に制限を設けない一般的な問題はNP困難である^[3]^[4]。

命題

数学的には、問題は次のように定式化される。

互いに素（すなわち

gcd (a 1, a 2, \dots, a n) = 1

）である正の整数

a 1, a 2, \dots, a n

が与えられたとき、これらの数の整数の和（錐結合）、つまり

k 1 a 1 + k 2 a 2 + \dots + k n a n

で表現できない最大の整数を求めよ。ここで係数

k 1, k 2, \dots, k n

は非負整数とする。

この最大の整数を集合 ${a 1, a 2, \dots, a n}$ のフロベニウス数と呼び、 $g (a 1, a 2, \dots, a n)$ で表される。

フロベニウス数が存在するためには、最大公約数 (GCD) が1であることが必要である。最大公約数が1でないならば、最大公約数の倍数ではないすべての整数は、その集合の要素の錐結合で表せないだけでなく、線形和としても表現できないため、最大の整数は存在しない。例えば、4円と6円の2種類の硬貨では、最大公約数は2（円）になるため、何枚組み合わせても奇数円を作ることはできない。一方、最大公約数が1である場合は常に、 ${a 1, a 2, \dots, a n}$ の錐結合で表せない整数の集合は、シューアの定理（英語版）により限りがあるため、フロベニウス数が存在する。

小さいnに対するフロベニウス数

コインの種類 n が 1 または 2 の場合のフロベニウス数は閉形式を持つことが知られている。n が 2 より大きい場合に対する閉形式での解は知られていない^[5]。

n = 1

n = 1 ならば、最大公約数が1であるという条件より a₁ = 1 の場合にのみこの問題が成立し、そしてすべての自然数を作ることができる。そのため、フロベニウス数は存在しない。

n = 2

n = 2 ならば、フロベニウス数は $g(a_{1},a_{2})=a_{1}a_{2}-a_{1}-a_{2}$

20個入りの、チキンマックナゲット

有名な特別な場合に、チキンマックナゲット数がある。この問題はHenri PicciottoがAnita Wahと共著で代数の教科書に書いたことで導入された^[16]。1980年代にPicciottoはマクドナルドで息子と食事をしながらこの問題を考え、ナプキン上で解決した。チキンマックナゲット数は、チキンマックナゲットのセットを購入することで揃えられるチキンマックナゲットの総数である。ハッピーセットサイズのナゲットの導入前のイギリスでは、6, 9, 20個入りのナゲットが提供されていた。

シューアの定理より、6, 9, 20は（6と9は公約数3を持つが）互いに素であるため、十分大きい整数はこれら3つの線形結合で表せる。したがって、最大の非チキンマックナゲット数（チキンマックナゲット数ではない整数）が存在する。すなわち、次の例外を除いてすべての正の整数はチキンマックナゲット数であるといえる。

1, 2, 3, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 22, 23, 25, 28, 31, 34, 37, 43

（オンライン整数列大辞典の数列 A065003）

Total	0	1	2	3	4	5
+0	0:0,0,0	1:—	2:—	3:—	4:—	5:—
+6	6:1,0,0	7:—	8:—	9:0,1,0	10:—	11:—
+12	12:2,0,0	13:—	14:—	15:1,1,0	16:—	17:—
+18	18:3,0,0	19:—	20:0,0,1	21:2,1,0	22:—	23:—
+24	24:4,0,0	25: —	26:1,0,1	27:3,1,0	28: —	29:0,1,1
+30	30:5,0,0	31: —	32:2,0,1	33:4,1,0	34: —	35:1,1,1
+36	36:6,0,0	37: —	38:3,0,1	39:5,1,0	40:0,0,2	41:2,1,1
+42	42:7,0,0	43: —	44:4,0,1	45:6,1,0	46:1,0,2	47:3,1,1
+48	48:8,0,0	49:0,1,2	50:5,0,1	51:7,1,0	52:2,0,2	53:4,1,1
+54	54:9,0,0	55:1,1,2	56:6,0,1	57:8,1,0	58:3,0,2	59:5,1,1
0から59個に対する、チキンマックナゲットの買い方。コロンの右の3個の数は、それぞれ 6, 9, 20個のセットを買う数。

上記の表より、最大の非チキンマックナゲット数は43である^[17]。43より大きい任意の整数がチキンマックナゲット数であることは、以下の自然数の分割のいずれかに6を適当な回数だけ足し合わせることで確かめられる。

{\begin{array}{ll}44&=6+9+9+20\\45&=9+9+9+9+9\\46&=6+20+20\\47&=9+9+9+20\\48&=6+6+9+9+9+9\\49&=9+20+20\end{array}}

[1]

[2]

[3]

[4]

[5]

[16]

[17]

フロベニウスの硬貨交換問題とは？ わかりやすく解説