コインの問題

もし${\displaystyle n=1}$そうすれば、私たちは${\displaystyle a_{1}=1}$それによって、すべての自然数を構成できるようになる。

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

方程式の別の形式は${\displaystyle g(a_{1},a_{2})}$これは、 Skupień ^{[ 7 ]}によって次の命題で与えられています。${\displaystyle a_{1},a_{2}\in \mathbb {N} }$そして${\displaystyle \gcd(a_{1},a_{2})=1}$次に、それぞれについて${\displaystyle n\geq (a_{1}-1)(a_{2}-1)}$非負整数のペアはちょうど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}}$。 確かに、$\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}$方程式と不等式を満たす）。

同様に、${\displaystyle u,v}$満足${\displaystyle Nk=ua+vb}$ そして${\displaystyle 0\leq u<b}$.これでこれらの式を追加して書くことができます${\displaystyle N=(u+x)a+(y+v)b}$使用${\displaystyle N=ab-ab}$収量${\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 Nk=ua+vb}$表現可能である場合。${\displaystyle v}$否定的であるということは、${\displaystyle k}$表現可能である。

したがって、任意の非負整数に対して${\displaystyle k\in [0,ab-ab]}$我々は、${\displaystyle k}$または${\displaystyle (ab-ab)-k}$表現可能（そしてこれらは異なる、なぜなら${\displaystyle ab-ab}$整数は奇数でなければならない${\displaystyle a,b}$は互いに素である）。これは、与えられた範囲の整数の半分が表現可能であることを示している。${\displaystyle (ab-a-b+1)=(a-1)(b-1)}$範囲内の整数${\displaystyle [0,ab-ab]}$これにより、望ましい結果が得られます。

3つの数値については公式^{[ 8 ]}と高速アルゴリズム^{[ 9 ]}が知られていますが、手計算で行うと非常に面倒な場合があります。

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}}}}$

比較的シャープです。^{[ 10 ]}${\displaystyle f}$ここに修正フロベニウス数があります。これは、正の整数の線形結合では表現できない最大の整数です。${\displaystyle a_{1},a_{2},a_{3}}$）

漸近平均挙動${\displaystyle f}$3 つの変数については、次のようにも呼ばれます。^{[ 11 ]}

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

等差数列の整数の集合のフロベニウス数を求める簡単な公式が存在する。^{[ 1 ]： 59-60} 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}$上記のケースは、この公式の特殊なケースとして表現できる。

万が一${\displaystyle a>w^{2}-3w+1}$要素の任意の部分集合を省略できます${\displaystyle a+2d,a+3d,...,a+(w-3)d,a+(w-2)d}$等差数列から、フロベニウス数の公式は同じままです。^{[ 14 ]}

等比数列の集合のフロベニウス数についても、閉形式解が存在する。^{[ 15 ]} 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}}.}$

変数間の対称性も示すより単純な式は次のとおりです。正の整数が与えられた場合${\displaystyle a,b,k}$、 と${\displaystyle \gcd(a,b)=1,}$させて${\displaystyle A_{k}(a,b)=\{a^{k},a^{k-1}b,\ldots ,b^{k}\}}$.それから^{[ 16 ]}

${\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にパズルとして掲載され^{[ 17 ]}、アニタ・ワーと共著した代数学の教科書にも含まれています^{[ 18 ]} 。ピチオットは、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である。^{[ 19 ]} 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個入りの箱を複数個購入し、さらに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以外のすべてのスコアが可能です。これは、スコリガミの概念に直接関係しています。

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

ペトリネットは、分散コンピューティングにおける問題をモデル化するのに役立ちます。特定の種類のペトリネット、すなわち保守的な重み付き回路の場合、与えられた重みを持つ可能な「状態」または「マーキング」のうち、どれが「生存」しているかを知りたい場合があります。最小の生存重みを決定する問題は、フロベニウス問題と同等です。

1変数多項式をあるべき乗にすると、その多項式の指数を整数の集合として扱うことができます。展開された多項式には、次のべき乗が含まれます。${\displaystyle x}$ある指数（GCD=1の場合）のフロベニウス数よりも大きい、例えば、${\displaystyle (1+x^{6}+x^{7})^{n}}$集合は{6, 7}であり、フロベニウス数は 29 なので、項は${\displaystyle x^{29}}$いかなる値でも表示されません${\displaystyle n}$しかし、いくつかの価値は${\displaystyle n}$権限のある条件を与える${\displaystyle x}$29より大きい。指数の最大公約数が1でない場合、ある値より大きいべき乗は、最大公約数の倍数である場合にのみ表示されます。たとえば、${\displaystyle (1+x^{9}+x^{15})^{n}}$、24、27、...のべき乗がいくつかの値で現れます。${\displaystyle n}$ただし、3の倍数でない24より大きい値（1～8、10～14、16、17、19～23の小さい値も含む）は使用しない。