コインの問題

数学において、コイン問題（数学者フェルディナント・フロベニウスにちなんでフロベニウスコイン問題またはフロベニウス問題とも呼ばれる）は、指定された額面のコインのみを使用して取得できない最大の金額を求める数学の問題です。^[1]たとえば、3単位と5単位のコインのみを使用して取得できない最大の金額は7単位です。与えられたコインの額面の集合に対するこの問題の解は、その集合のフロベニウス数と呼ばれます。フロベニウス数は、コインの額面の集合が互いに素である限り存在します。

異なる硬貨の額面が 2 つしかない場合、および（この 2 つの数の最大公約数が 1 である）には、フロベニウス数の明示的な公式が存在する。硬貨の額面が 3 つ以上の場合、明示的な公式は知られていない。しかし、硬貨の額面数が固定されている場合、多項式時間（入力を形成する硬貨の額面数の対数）でフロベニウス数を計算するアルゴリズムが存在する。 ^{[2]硬貨の額面}数で多項式時間である既知のアルゴリズムはなく、硬貨の額面数が任意の数である場合の一般的な問題はNP 困難である。^{[3] [4]}${\displaystyle x}$${\displaystyle y}$${\displaystyle xy-xy}$

フロベニウスはコイン問題を高速道路の車線に例えました。

数学的に言えば、この問題は次のように表現できます。

gcdとなる正の整数が与えられた場合、これらの数の整数 円錐結合、つまり合計として表すことができない最大の整数を見つけます。${\displaystyle a_{1},a_{2},\dots ,a_{n}}$${\displaystyle (a_{1},a_{2},\dots ,a_{n})=1}$${\displaystyle k_{1}a_{1}+k_{2}a_{2}+\dots +k_{n}a_{n}}$

ここで、は負でない整数です。${\displaystyle k_{1},k_{2},\dots ,k_{n}}$

この最大の整数は集合のフロベニウス数と呼ばれ、通常は次のように表される。${\displaystyle \{a_{1},a_{2},\dots ,a_{n}\}}$${\displaystyle g(a_{1},a_{2},\dots ,a_{n})}$

フロベニウス数が存在するかどうかは、最大公約数 (GCD) が 1 であるという条件によって決まります。実際、すべての場合において、考えられる和は GCD の倍数です。したがって、それが 1 でない場合は、和として得られない任意の大きな数が常に存在します。たとえば、6 セントと 14 セントの価値がある 2 種類のコインがある場合、GCD は 2 になり、そのようなコインをいくつ組み合わせても、その和が奇数になることはありません。さらに、2、4、8、10、16、22 ( m=24未満) の偶数も形成されません。一方、GCD が 1 の場合は常に、 の円錐結合として表すことができない整数の集合は、シューアの定理に従って制限されるため、フロベニウス数が存在することになります。 ${\displaystyle \{a_{1},a_{2},\dots ,a_{n}\}}$

コイン問題には、n = 1または2の場合にのみ閉じた形式の解が存在する。n  > 2 の場合の閉じた形式の解は知られていない。^[4]

ならば、すべての自然数を形成できるように が 成り立つ必要があります。${\displaystyle n=1}$${\displaystyle a_{1}=1}$

の場合、フロベニウス数は1882年にジェームズ・ジョセフ・シルベスターによって発見された式 から求めることができます。 ^{[5] [注 1]} シルベスターは、この場合、表現できない（正の）整数の合計が存在することも実証しました。 ${\displaystyle n=2}$${\displaystyle g(a_{1},a_{2})=a_{1}a_{2}-a_{1}-a_{2}}$${\displaystyle N(a_{1},a_{2})=(a_{1}-1)(a_{2}-1)/2}$

に対する等式の別の形式は、Skupień ^[8]によって次の命題で与えられています: およびならば、各 に対して、およびとなる非負整数のペアがちょうど1つ存在します。 ${\displaystyle g(a_{1},a_{2})}$${\displaystyle a_{1},a_{2}\in \mathbb {N} }$${\displaystyle \gcd(a_{1},a_{2})=1}$${\displaystyle n\geq (a_{1}-1)(a_{2}-1)}$${\displaystyle \rho}$${\displaystyle \sigma}$${\displaystyle \sigma <a_{1}}$${\displaystyle n=\rho a_{1}+\sigma a_{2}}$

公式は次のように証明されます。 数 を構築したいとします。 なので、 のすべての整数はを法として互いに異なります。したがって、任意の整数はこれらの剰余のいずれかを法として合同でなければなりません。特に、 を取ると、の一意の値と となる一意の整数があります。整理すると、となる非負の整数が得られます。実際、であるためです。 ${\displaystyle n\geq (a_{1}-1)(a_{2}-1)}$${\displaystyle \gcd(a_{1},a_{2})=1}$${\displaystyle n-ja_{2}}$${\displaystyle j=0,1,\ldots ,a_{1}-1}$${\displaystyle a_{1}}$${\displaystyle m}$${\displaystyle a_{1}}$${\displaystyle m=a_{1}}$${\displaystyle j=\sigma \geq 0}$${\displaystyle t}$${\displaystyle a_{1}=n-\sigma a_{2}+ta_{1}}$${\displaystyle \rho =1-t}$${\displaystyle n=\rho a_{1}+\sigma a_{2}}$${\displaystyle \rho \geq 0}$${\displaystyle \rho a_{1}=n-\sigma a_{2}\geq (a_{1}-1)(a_{2}-1)-(a_{1}-1)a_{2}=-a_{1}+1>(-1)a_{1}}$

整数のちょうど半分が非負整数の線形結合として表現可能であることを示すには、まず、整数が表現可能であれば、 は表現できないことを示します。 ここで、${\displaystyle 0,1,\ldots ,ab-ab}$${\displaystyle k\in [0,ab-ab]}$${\displaystyle Nk}$${\displaystyle N=ab-ab}$

次に、逆も真であることが示されます。つまり、が表現できない場合は、 が表現できます。これを示すには、 という事実を使用します。これにより、 と書くことができます。必要に応じての倍数を追加して係数を削減および並べ替えると、 と仮定できます(実際、これは方程式と不等式を満たす 唯一の です)。${\displaystyle k}$${\displaystyle Nk}$${\displaystyle \gcd(a,b)=1}$${\displaystyle k=xa+yb}$${\displaystyle ab}$${\displaystyle 0\leq x<b}$${\displaystyle x}$${\displaystyle x}$

同様に、およびを満足するを取ります。ここで、これらの式を加えて と書くことができ、 を使用して となります。整数はであるため、正です。実際、 の左辺はで割り切れ、 であるため、は で割り切れる必要があります。しかし、 であるため、 となります。したがって となります。これを に代入して両辺から引くと となります。したがってとなります。これは を意味し、つまりまたは のちょうど 1 つが負であることを意味します。が負の場合、 となり、つまり が表現可能であることを意味します。 が負の場合、 が表現可能であることを意味します。 ${\displaystyle u,v}$${\displaystyle N-k=ua+vb}$${\displaystyle 0\leq u<b}$${\displaystyle N=(u+x)a+(y+v)b}$${\displaystyle N=ab-a-b}$${\displaystyle ab-b(1+y+v)=a(x+u+1)}$${\displaystyle x+u+1}$${\displaystyle x,u\geq 0}$${\displaystyle ab-b(1+y+v)=a(x+u+1)}$${\displaystyle b}$${\displaystyle (a,b)=1}$${\displaystyle x+u+1}$${\displaystyle b}$${\displaystyle x,u\leq b-1}$${\displaystyle x+u+1\leq 2b-1}$${\displaystyle x+u+1=b}$${\displaystyle ab-b(1+y+v)=a(x+u+1)}$${\displaystyle ab}$${\displaystyle b(1+y+v)=0}$${\displaystyle 1+y+v=0}$${\displaystyle y+v=-1}$${\displaystyle y}$${\displaystyle v}$${\displaystyle y}$${\displaystyle v\geq 0}$${\displaystyle N-k=ua+vb}$${\displaystyle v}$${\displaystyle k}$

したがって、任意の非負整数 について、または のうち正確に 1 つが表現可能であることがわかります(整数 は互いに素であるため は奇数でなければならないため、これらは異なるものです)。これは、指定された範囲内の整数の半分が表現可能であることを示しています。範囲 には整数があるため、これは目的の結果をもたらします。 ${\displaystyle k\in [0,ab-a-b]}$${\displaystyle k}$${\displaystyle (ab-a-b)-k}$${\displaystyle ab-a-b}$${\displaystyle a,b}$${\displaystyle (ab-a-b+1)=(a-1)(b-1)}$${\displaystyle [0,ab-a-b]}$

3つの数値については公式^[9]と高速アルゴリズム^[10]が知られていますが、手作業で計算すると非常に面倒になります。

n = 3のときのフロベニウス数のより単純な下限と上限も決定されている。デイヴィソンによる漸近下限は

${\displaystyle f(a_{1},a_{2},a_{3})\equiv g(a_{1},a_{2},a_{3})+a_{1}+a_{2}+a_{3}\geq {\sqrt {3a_{1}a_{2}a_{3}}}}$

は比較的シャープです。^[11]（ここでは修正フロベニウス数で、の正の整数線形結合で表現できない最大の整数です。）実際の極限（ のパラメトリック関係で定義される）と比較すると、のときの近似値は真の値よりわずか 1 小さいことがわかります。 （ の値が互いに素であり、他の要素によって表現できない）同様のパラメトリック上限はであると推測されます。 ${\displaystyle f}$${\displaystyle a_{1},a_{2},a_{3}}$${\displaystyle f(z(i))=9i^{2}+54i+79}$${\displaystyle z(i)=a_{1}a_{2}a_{3}=(3i+7)(3i+10)(3i^{2}+19i+29)}$${\displaystyle i\rightarrow \infty }$${\displaystyle a_{1},a_{2},a_{3}}$${\displaystyle f(z(i))=6i^{2}+19i+13}$${\displaystyle z(i)=a_{1}a_{2}a_{3}=(3i+2)(3i+3)(6i+7)}$

3変数の漸近平均挙動は次のようにも知られています: ^[12]${\displaystyle f}$

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

1978年、ウィルフは互いに素な整数とそれらのフロベニウス数が与えられたとき、 ${\displaystyle a_{1}<a_{2}<...<a_{d}}$${\displaystyle F}$

${\displaystyle d\geq {\frac {F+1}{F+1-g}},}$

ここで、は表現できない正の整数の総数を表す。^[13] 2015年に、この漸近版がモスカリエロとサマルターノによって証明された。^[14]${\displaystyle g}$

等差数列の整数集合のフロベニウス数を求める簡単な公式が存在する。^[15] gcd( a ,  d )=1 となる整数a , d , wが与えられると、

${\displaystyle g(a,a+d,a+2d,\dots ,a+wd)=\left(\left\lfloor {\frac {a-2}{w}}\right\rfloor \right)a+d(a-1)}$

上記のケースは、この式の特殊なケースとして表現できます。 ${\displaystyle n=2}$

の場合には、算術シーケンスから要素の任意のサブセットを省略することができ、フロベニウス数の式は同じままです。^[16]${\displaystyle a>w^{2}-3w+1}$${\displaystyle a+2d,a+3d,...,a+(w-3)d,a+(w-2)d}$

等比数列の集合のフロベニウス数に対する閉じた形式の解も存在する。^[17] gcd( m ,  n )=1 となる整数m , n , kが与えられると、

${\displaystyle g(m^{k},m^{k-1}n,m^{k-2}n^{2},\dots ,n^{k})=n^{k-1}(mn-m-n)+{\frac {m^{2}(n-1)(m^{k-1}-n^{k-1})}{m-n}}.}$

変数間の対称性も示すより単純な式は次の通りである。正の整数が与えられ、 とすると、^[18]${\displaystyle a,b,k}$${\displaystyle \gcd(a,b)=1,}$${\displaystyle A_{k}(a,b)=\{a^{k},a^{k-1}b,\ldots ,b^{k}\}}$

${\displaystyle g(A_{k}(a,b))={\sigma }_{k+1}(a,b)-{\sigma }_{k}(a,b)-(a^{k+1}+b^{k+1}),}$

ここで、はすべての整数の合計を表します。${\displaystyle {\sigma }_{k}(a,b)}$${\displaystyle A_{k}(a,b).}$

コイン問題の特殊なケースの 1 つは、マックナゲット数と呼ばれることもあります。コイン問題のマックナゲット版は、アンリ・ピチョットによって導入されました。彼はこれを1987 年にGames Magazineにパズルとして掲載し、 ^[19]アニタ・ワと共著した代数の教科書に掲載しました。^[20]ピチョットは 1980 年代に息子とマクドナルドで食事をしているときにこの応用を思いつき、ナプキンに問題を解きました。マックナゲット数とは、任意の数の箱に入っているマクドナルドの チキンマックナゲットの合計数です。英国では、オリジナルの箱 (ハッピーミールサイズのナゲット ボックスが導入される前) には 6 個、9 個、20 個が入っていました。

シューアの定理によれば、6、9、20 は（集合的に）互いに素なので、十分に大きい整数は、これら 3 つの（非負の整数）線形結合として表すことができます。したがって、最大の非マクナゲット数が存在し、それより大きい整数はすべてマクナゲット数です。つまり、有限個の例外を除いて、すべての正の整数はマクナゲット数です。

1、2、3、4、5、7、8、10、11、13、14、16、17、19、22、23、25、28、31、34、37、および43（OEISのシーケンスA065003）。

したがって、最大の非マクナゲット数は43である。^{[21] 43より大きい整数はマクナゲット数であるという事実は、次の}整数分割を考えるとわかる。

${\displaystyle 44=6+6+6+6+20}$

${\displaystyle 45=9+9+9+9+9}$

${\displaystyle 46=6+20+20}$

${\displaystyle 47=9+9+9+20}$

${\displaystyle 48=6+6+9+9+9+9}$

${\displaystyle 49=9+20+20}$

より大きな整数は、上記の適切なパーティションに 6 をいくつか追加することで得られます。簡単なチェックにより、43 個のマックナゲットは実際には購入 できないことがわかります。

1. 6 と 9 のボックスだけでは 43 を形成できません。これらは 3 の倍数しか作成できないためです (3 自体は例外)。
2. 20のボックスを1つ含めても役に立ちません。必要な余り（23）も3の倍数ではないからです。
3. 20 個入りの箱を 1 つ以上、さらにサイズ 6 以上の箱を追加しても、マックナゲットの合計が 43 個になるのは明らかです。

ハッピーミールサイズのナゲットボックスが 4 ピースになって以来、マックナゲット以外の最大数は 11 です。9 ピースサイズが 10 ピースサイズに置き換えられた国では、奇数は作れないため、マックナゲット以外の最大数は存在しません。

ラグビーユニオンでは、ペナルティゴール（3点）、ドロップゴール（3点）、トライ（5点）、コンバートトライ（7点）の4種類の得点がある。これらを組み合わせることで、1、2、4点を除くあらゆる合計得点が可能となる。ラグビーセブンズでは、4種類の得点方法すべてが認められているものの、ペナルティゴールの試みはまれで、ドロップゴールはほとんど知られていない。つまり、チームの得点は、ほとんどの場合、トライ（5点）とコンバートトライ（7点）の倍数で構成される。次の得点（1、2、4に加えて）は、5と7の倍数では作れないため、セブンズではほとんど見られない：3、6、8、9、11、13、16、18、23。例として、2014-15セブンズワールドシリーズのどの試合でも、これらの得点は記録されなかった。

同様に、アメリカンフットボールでは、タッチダウン後に相手チームがコンバージョンを試みた際にセーフティが与えられる場合のみ、チームがちょうど 1 ポイントを獲得できます(この場合、値は 6)。通常のプレイからのセーフティには 2 ポイントが与えられ、フィールド ゴールには 3 ポイントが与えられるため、1–0、1–1、2–1、3–1、4–1、5–1、7–1 以外のすべてのスコアが可能です。

Shellsortアルゴリズムは、時間計算量が現在未解決の問題となっているソート アルゴリズムです。最悪の場合の計算量には上限があり、これは与えられた正の整数のシーケンスのフロベニウス数で表すことができます。

ペトリ ネットは、分散コンピューティングにおける問題をモデル化するのに役立ちます。特定の種類のペトリ ネット、つまり保守的な重み付け回路の場合、特定の重みを持つ「状態」または「マーク」のうち、どの「ライブ」であるかを知りたい場合があります。最小のライブ ウェイトを決定する問題は、フロベニウス問題に相当します。

一変数多項式をあるべき乗すると、多項式の指数を整数の集合として扱うことができます。展開された多項式には、ある指数に対してフロベニウス数よりも大きいべき乗が含まれます (GCD=1 の場合)。たとえば、の集合は{6, 7}であり、そのフロベニウス数は 29 です。したがって、 の項はのどの値に対しても出現しませんが、 のいくつかの値は29 より大きいべき乗を持つ項を生成します。指数の GCD が 1 でない場合、ある値より大きいべき乗は、それが GCD の倍数である場合にのみ出現します。たとえば、 の場合、 のいくつかの値に対して 24、27、... のべき乗が出現しますが、3 の倍数でない 24 より大きい値 (およびより小さい値 1-8、10-14、16、17、19-23) は決して出現しません。 ${\displaystyle x}$${\displaystyle (1+x^{6}+x^{7})^{n}}$${\displaystyle x^{29}}$${\displaystyle n}$${\displaystyle n}$${\displaystyle x}$${\displaystyle (1+x^{9}+x^{15})^{n}}$${\displaystyle n}$

• 切手問題
• 変化をもたらす問題
• 銀貨
• 数値半群

• Tuenter, Hans JH (2006 年 4 月)。「フロベニウス問題、整数の累乗の和、ベルヌーイ数の反復」。Journal of Number Theory。117 ( 2): 376–386。doi : 10.1016 / j.jnt.2005.06.015。MR  2213771。Zbl 1097.11010  。

• 43 チキンマックナゲットの注文方法 – Numberphile