フロベニウスの硬貨交換問題

原文と比べた結果、この記事には多数の（または内容の大部分に影響ある）誤訳があることが判明しています。情報の利用には注意してください。 正確な表現に改訳できる方を求めています。 (2019年1月)

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

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

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

互いに素（すなわち gcd (a₁, a₂, …, a_n) = 1）である正の整数 a₁, a₂, …, a_n が与えられたとき、これらの数の整数の和（錐結合）、つまり

k₁a₁ + k₂a₂ + … + k_na_n

で表現できない最大の整数を求めよ。ここで係数 k₁, k₂, …, k_n は非負整数とする。

この最大の整数を集合 {a₁, a₂, …, a_n} のフロベニウス数と呼び、g(a₁, a₂, …, a_n) で表される。

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

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

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

n = 2 ならば、フロベニウス数は ${\displaystyle g(a_{1},a_{2})=a_{1}a_{2}-a_{1}-a_{2}}$ である。この式は、ジェームス・ジョセフ・シルベスターが1882年に発見した^[6]。時に、別の文献^[7]が誤ってこの定理の初出とされることがある。この文献でシルベスターは、自らの定理をレクリエーション数学の問題として出した^[8]（ただし、フロベニウス数の公式とは明示しなかった）。またそこで、この場合に${\displaystyle N(a_{1},a_{2})={\frac {(a_{1}-1)(a_{2}-1)}{2}}}$ 個の表せない自然数が存在することも述べている（シルベスターの閉形式定理）。

Skupieńは、フロベニウス数に対して別の形の公式を与えた^[9]。Skupieńは、「最大公約数が1である2個の自然数 a₁ と a₂ がある場合、${\displaystyle (a_{1}-1)(a_{2}-1)}$ 以上の任意の自然数 mに対して、非負整数の ρ と σ を用いて、${\displaystyle m=\rho a_{1}+\sigma a_{2}}$（ただし${\displaystyle \sigma <a_{1}}$）という表現が可能である。」という形式で述べた。

この公式は以下のように証明できる。

${\displaystyle m\geq (a_{1}-1)(a_{2}-1)}$ を表現したいとする。a₁, a₂ の最大公約数は1であるため、${\displaystyle \sigma =0,1,\cdots ,a_{1}-1}$ に対して ${\displaystyle m-\sigma a_{2}}$ はすべて a₁ を法として互いに異なる。したがって、${\displaystyle m=\rho a_{1}+\sigma a_{2}}$ となるようなただ一つの σ と、非負整数 ρ が存在する。ρ が非負であるのは、

${\displaystyle \rho a_{1}=m-\sigma a_{2}\geq (a_{1}-1)(a_{2}-1)-(a_{1}-1)a_{2}=-a_{1}+1}$

から分かる。

n = 3 に対するフロベニウス数を求める高速なアルゴリズムは知られている（数値半群を参照）。しかし、手作業での計算は非常に面倒である。また、n = 3 のフロベニウス数に対する下限および上限はすでに得られている。Davisonによって与えられたフロベニウス数の下限は

${\displaystyle g(a_{1},a_{2},a_{3})\geq {\sqrt {3a_{1}a_{2}a_{3}}}-a_{1}-a_{2}-a_{3}}$

であることが知られている^[10]。

また、平均は

${\displaystyle g(a_{1},a_{2},a_{3})+a_{1}+a_{2}+a_{3}\sim {\frac {8}{\pi }}{\sqrt {a_{1}a_{2}a_{3}}}}$

に漸近することが知られている^[11]。また、この左辺は修正フロベニウス数と呼ばれる、正の整数の線形和で表現できない最大の整数である。

等差数列を要素とする整数の集合のフロベニウス数は簡単に求められる^[12]。いずれも整数の初項 a、等差 d、 s に対して、a と d の最大公約数が1であれば、

${\displaystyle g(a,a+d,a+2d,\cdots ,a+sd)=\left(\left\lfloor {\frac {a-2}{s}}\right\rfloor +1\right)a+(d-1)(a-1)-1}$

であり、前述の n = 2 の場合は、上式で d = a₂ − a₁, s = 1 とした特殊な場合に対応する。

等比数列を要素とする整数の集合のフロベニウス数の閉形式での解も存在する^[13]。いずれも整数のa, b, k に対して、a と b の最大公約数が1であれば、その要素は ${\displaystyle a^{k},a^{k-1}b,a^{k-2}b^{2},\cdots a^{2}b^{k-2},ab^{k-1},b^{k}}$ という対称な形となり、

${\displaystyle g(a^{k},a^{k-1}b,\cdots ,ab^{k-1},b^{k})=b^{k-1}(ab-a-b)+{\frac {a^{2}(b-1)(a^{k-1}-b^{k-1})}{a-b}}}$

である^[14]。

また、${\displaystyle \sigma _{k}(a,b)=a^{k}+a^{k-1}b+\cdots +ab^{k-1}+b^{k}}$とすると、${\displaystyle g(a^{k},a^{k-1}b,\cdots ab^{k-1},b^{k})=\sigma _{k+1}(a,b)-\sigma _{k}(a,b)-(a^{k+1}+b^{k+1})}$と簡潔に表せる^[15]。

有名な特別な場合に、チキンマックナゲット数がある。この問題は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）

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

${\displaystyle {\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}}}$

さらに、以下のように、43個ちょうどのチキンマックナゲットは購入できないことが示される。

1. 6個入と9個入のセットだけでは、3の倍数個しか購入できない（3個は不可能）ため、43個を購入できない。
2. 20個入を1セット購入すると、残りの23個が3の倍数ではないため、20個入のセットを1個だけ含めても43個を購入できない。
3. 20個入を2セット購入すると、残りの3個が購入できない（最小購入単位が6である）ため、43個ちょうどのチキンマックナゲットは購入できない。

4個入のハッピーセットのナゲットの発売以来、最大の非チキンマックナゲット数は11となった。9個入が10個入となる国では、奇数を作れないため、最大の非チキンマックナゲット数は存在しない。

ラグビーユニオンでは、4種類の得点：ペナルティゴール（3点）、ドロップゴール（3点）、トライ（5点）、コンバートトライ（7点）が存在する。これらのポイントを組み合わせることで、1、2、4以外の得点が可能である。7人制ラグビーでは、4種類の得点が存在するが、ペナルティゴールの試みはほとんど起きず、ドロップゴールはほとんど知られていない。つまり、得点はほとんどの場合、トライ（5点）の倍数とコンバートトライ（7点）の倍数で構成される。そのため7人制ラグビーでは1、2、4点以外にも、5と7の倍数から生じない3, 6, 8, 9, 11, 13, 16, 18, 23点はほとんど生じない。実際、これらの得点はどれも2014 - 15年シーズンのSevens World Seriesのどの試合でも記録されていない。

同様に、ナショナルフットボールリーグでは、チームが1点を獲得するための唯一の方法は、タッチダウン（6点）後にコンバージョンをしようとしたときに、相手チームに対してセイフティが与えられた場合である。通常のプレイからのセイフティに対しては2点が与えられ、フィールドゴールに対して3点が与えられるので、1−0, 1−1, 2−1, 3−1, 4−1, 5−1, 7−1以外の点数は実現可能である。

• 切手問題 - 限られた枚数の切手で表せない最小の整数
• シルバーコインゲーム（英語版）

• 『フロベニウスの硬貨交換問題』 - 高校数学の美しい物語
• How to order 43 Chicken McNuggets – Numberphile - YouTube