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

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

フロベニウスの硬貨交換問題は、いくつかの種類の硬貨が与えられたときに、それらを組み合わせては正確に表現できない（支払えない）最大の金額を求めるという数学の課題です。この問題は、19世紀の数学者フェルディナント・ゲオルク・フロベニウスにちなんで名付けられました。単に「フロベニウスの問題」と呼ばれることもあれば、「シルベスターの切手問題」という別名で知られることもあります。

この問題の答えとなる、表現できない最大の金額を「フロベニウス数」と呼びます。例えば、3円と5円の硬貨だけを使う場合を考えます。これらを組み合わせて支払える金額は、3円、5円、6円（3+3）、8円（3+5）、9円（3+3+3）、10円（5+5）、11円（3+3+5）、12円（3+3+3+3または5+7※7は無い）、13円（3+5+5）などと続いていきます。このとき、ぴったり支払えない最大の金額は7円です（1, 2, 4, 7円などは支払えません）。したがって、額面{3, 5}に対するフロベニウス数は7となります。

数学的背景

数学的には、この問題は次のように定式化されます。互いに素である（すなわち、それらの最大公約数G.C.D.が1である）ような正の整数 `a₁, a₂, ..., aₙ` が与えられたとき、これらの数を非負の整数 `k₁, k₂, ..., kₙ` を用いて `k₁a₁ + k₂a₂ + ... + kₙaₙ` という形の線形結合で表現できない最大の整数を求めます。この最大の整数が、集合 `{a₁, a₂, ..., aₙ}` のフロベニウス数 `g(a₁, a₂, ..., aₙ)` です。

フロベニウス数が存在するためには、与えられた数の集合の最大公約数が1であるという条件が不可欠です。もし最大公約数が1でない場合、その最大公約数の倍数ではないすべての整数は、たとえ負の係数を含めても線形結合で表現できないどころか、非負の係数ではなおさら表現できません。したがって、そのような場合は表現できない整数の集合に上限がなくなり、最大の整数、すなわちフロベニウス数は存在しません。例えば、4円と6円の硬貨だけでは、どんなに組み合わせても金額は必ず偶数（4k₁ + 6k₂ = 2(2k₁ + 3k₂)）になり、奇数円は決して支払えません。一方、最大公約数が1であれば、シューアの定理によって、表現できない正の整数の集合は有限であることが保証されており、フロベニウス数が存在します。

硬貨の種類数とフロベニウス数

フロベニウス数を求める難しさは、硬貨の種類数 `n` に依存します。

n = 1: 額面が1種類の場合、最大公約数が1であるためには額面は1である必要があります。1円硬貨があればすべての自然数を表現できるため、この場合のフロベニウス数は存在しません。

n = 2: 額面が `a₁` と `a₂` の2種類の場合 (`gcd(a₁, a₂)=1`)、フロベニウス数には簡単な閉形式の公式が存在します。これは `g(a₁, a₂) = a₁a₂ - a₁ - a₂` または `(a₁ - 1)(a₂ - 1) - 1` で与えられます。この公式はジェームス・ジョセフ・シルベスターによって1882年に発見されました。また、2種類の硬貨で表現できない正の整数の個数は `(a₁ - 1)(a₂ - 1) / 2` であることも知られています。

n >= 3: 硬貨の種類が3種類以上の場合、n=2のような一般的な閉形式の公式はまだ発見されていません。しかし、特定の構造を持つ集合（後述）や、限られた種類の数に対しては、フロベニウス数を計算するための効率的なアルゴリズムが存在します。特にn=3の場合は高速なアルゴリズムが知られており、数値半群の研究とも関連が深いです。また、フロベニウス数の下限や、値の大きさに関する漸近的な性質についても研究されています。

計算量の側面

一般的なフロベニウス数の計算は難しい問題とされています。硬貨の種類数 `n` に対して多項式時間で解けるようなアルゴリズムは現在まで見つかっておらず、任意の `n` に対する問題はNP困難に属すると考えられています。ただし、種類の数の対数に対しては多項式時間で計算できるアルゴリズムが存在します。

特殊な集合のフロベニウス数

額面の集合が特定の性質を持つ場合、フロベニウス数に対する比較的簡単な公式が得られることがあります。例えば、額面が等差数列や等比数列をなす場合などです。

具体例

チキンマックナゲット数: この問題の有名な応用例に、チキンマックナゲットの購入可能な総数に関する問題があります。これは、昔のイギリスのマクドナルドで提供されていたナゲットのセット（6個、9個、20個）に由来します。額面{6, 9, 20}の最大公約数は `gcd(6, 9, 20) = gcd(gcd(6, 9), 20) = gcd(3, 20) = 1` であるため、フロベニウス数が存在します。この場合のフロベニウス数は43であり、43より大きな任意の個数は、6個、9個、20個のセットを組み合わせて購入可能です。例えば、44 = 6 + 9 + 9 + 20, 45 = 9 x 5, 46 = 6 + 20 + 20, 47 = 9 + 9 + 9 + 20, 48 = 6 x 8, 49 = 9 + 20 + 20 のように表現できます。43個が購入できないことは、例えば20個のセットを0, 1, 2個使う場合それぞれについて、残りの個数（43, 23, 3）が6個と9個のセット（3の倍数）で表現できないことから確認できます。その後、4個入りのハッピーセットナゲットが導入された国では、額面が{4, 6, 9, 20}となり、フロベニウス数は11に変わりました。

ラグビーの得点: ラグビーユニオンでは、ペナルティゴールとドロップゴールが3点、トライが5点、コンバートトライが7点です。これらの得点源{3, 5, 7}は互いに素なので、フロベニウス数が存在し、特定の小さな点数（1, 2, 4点など）以外はすべて達成可能です。

NFLの得点: ナショナルフットボールリーグの得点（タッチダウン6点、フィールドゴール3点、セイフティ2点、タッチダウン後のコンバージョンセイフティ1点）も同様に、これらの点数を組み合わせることで可能な総得点に関する問題と関連付けられます。額面{1, 2, 3, 6}は互いに素であるため、フロベニウス数が存在し、特定の極めて稀なケースを除き、ほとんどのスコアが理論上達成可能です。

フロベニウスの硬貨交換問題は、組合せ論や数論における古典的でありながら、応用例も豊富な興味深いテーマです。

関連項目

切手問題
シルバーコインゲーム

参考文献

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

もう一度検索