コインの問題

Mathematical problem

2 ペンスと 5 ペンスの硬貨だけでは 3 ペンスは作れませんが、それ以上の整数額を作ることは可能です。

2ペンス硬貨と5ペンス硬貨のフロベニウス硬貨問題をグラフで視覚化しました。
傾斜線は2 x +5 y = nのグラフを表します。ここで、 nはペンス単位の合計、xとyはそれぞれ2ペンス硬貨と5ペンス硬貨の非負数です。
直線上の点は、与えられた合計に対して2ペンスと5ペンスの組み合わせを表します（緑）。
直線上に複数の点がある場合は、複数の組み合わせが可能です（青）。n =
1または3の直線のみに点がありません（赤）。

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

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

声明

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

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 の倍数です。したがって、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

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

n= 1

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

n= 2

の場合、フロベニウス数は という式から求めることができます。この式は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-a-b}$ ${\displaystyle k\in [0,ab-a-b]}$ ${\displaystyle N-k}$ ${\displaystyle N=ab-a-b}$

次に、逆もまた真であることを示す。すなわち、が表現可能でなければ、 は表現可能である。これを示すには、 という事実を用いる。これにより、 と書くことができる。必要に応じて の倍数を加えて係数を縮約し、並べ替えることで、 と仮定することができる（実際、これは方程式と不等式を満たす唯一の である）。 ${\displaystyle k}$ ${\displaystyle N-k}$ ${\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}$

したがって、任意の非負整数 に対して、またはのどちらか一方が表現可能であることがわかります（そして、これらは互いに素であるためは奇数でなければならないため、これらは異なるものです）。これは、与えられた範囲内の整数の半分が表現可能であることを示しています。範囲 には整数が存在するため、これは望ましい結果をもたらします。 ${\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]}$

n= 3

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]（ここでは修正フロベニウス数であり、の正の整数線形結合で表すことができない最大の整数である。） ${\displaystyle f}$ ${\displaystyle a_{1},a_{2},a_{3}}$

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

例と応用

マクナゲット番号

マクドナルドのチキンマックナゲット20個入り箱

コイン問題の特殊なケースの 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）。

合計	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個のナゲットを含むボックスの組み合わせの可能なセット。各トリプレットは、それぞれ6、9、20個のボックスの 数を表します。

したがって、マクナゲット数以外の最大の数は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を除く任意の合計得点が可能となる。7人制ラグビーでは、4種類の得点方法すべてが認められているが、ペナルティゴールが試みられることは稀で、ドロップゴールはほとんど知られていない。つまり、チームの得点は、ほぼ常にトライ（5点）とコンバージョントライ（7点）の倍数で構成される。次の得点（1、2、4に加えて）は、5と7の倍数では作ることができず、したがって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以外のスコアは可能です。これはスコリガミの概念に直接関係しています。

シェルソートの時間計算量

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

最小生体重問題

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

多項式の拡張されたべき乗の項

一変数多項式をあるべき乗にすると、多項式の指数を整数の集合として扱うことができます。展開された多項式には、ある指数（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}$

参照

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

注記

1. 元の出典は時々誤って引用されるが、^[6]では著者は定理を娯楽問題として提示した^[7]（そしてフロベニウス数の式を明示的に述べていない）。

参考文献

1. J. ラミレス・アルフォンシン (2005)。ディオファンティノス・フロベニウス問題。オックスフォード大学プレス。
2. ラヴィ・カンナン (1992)。 「格子は多面体とフロベニウス問題を変換する」。コンビナトリカ。12 (2): 161–177。土井:10.1007/BF01204720。S2CID  19200821。
3. D. Beihoffer; J. Hendry; A. Nijenhuis; S. Wagon (2005). 「フロベニウス数のための高速アルゴリズム」. Electronic Journal of Combinatorics . 12 : R27. doi : 10.37236/1924 .
4. ワイスタイン、エリック W.「コインの問題」。マスワールド。
5. シルベスター、ジェームズ・ジョセフ (1882). 「部分不変量、すなわち無限秩序の二元量子論に対する半不変量について」.アメリカ数学ジャーナル. 5 (1): 134. doi :10.2307/2369536. JSTOR  2369536.
6. シルベスター、ジェームズ・ジョセフ (1884). 「質問7382」.エデュケーショナル・タイムズからの数学の問題. 41 : 21.
7. J. ラミレス・アルフォンシン (2005)。ディオファンティノス・フロベニウス問題。オックスフォード大学プレス。 p. 13.
8. スクピエン、ズジスワフ(1993)。 「シルベスターとフロベニウスの問題の一般化」(PDF)。アクタ算術。 LXV.4 (4): 353–366 .土井: 10.4064/aa-65-4-353-366。
9. Tripathi, A. (2017). 「3変数フロベニウス数の公式」. Journal of Number Theory . 170 : 368–389 . doi : 10.1016/j.jnt.2016.05.027 .
10. このようなアルゴリズムの詳細については、「埋め込み次元が 3 の数値半群」を参照してください。
11. M. Beck; S. Zacks (2004). 「フロベニウスの線形ディオファントス問題に対する洗練された上限値」. Adv. Appl. Math . 32 (3): 454– 467. arXiv : math/0305420 . doi :10.1016/S0196-8858(03)00055-1. S2CID  119174157.
12. Ustinov, A. (2009). 「3引数を持つフロベニウス数の弱漸近性に関するアーノルド問題の解」. Sbornik: 数学. 200 (4): 131– 160. Bibcode :2009SbMat.200..597U. doi :10.1070/SM2009v200n04ABEH004011.
13. Wilf, HS (1978). 「『貨幣交換問題』に対する光環アルゴリズム」 .アメリカ数学月刊誌. 85 (7): 562– 565. doi :10.2307/2320864. JSTOR  2320864.
14. Moscariello, A.; Sammartano, A. (2015). 「ウィルフによるフロベニウス数に関する予想について」. Mathematische Zeitschrift . 280 ( 1– 2): 47– 53. arXiv : 1408.5331 . doi :10.1007/s00209-015-1412-0.
15. ラミレス・アルフォンシン、ホルヘ (2005).ディオファンティノス・フロベニウス問題。オックスフォード大学出版局。59～ 60ページ 。
16. Lee, SH; O'neill, C.; Van Over, B. (2019). 「一部の生成子を省略した算術数値モノイドについて」. Semigroup Forum . 98 (2): 315– 326. arXiv : 1712.06741 . doi :10.1007/s00233-018-9952-3. S2CID  119143449.
17. Ong, Darren C.; Ponomarenko, Vadim (2008). 「幾何列のフロベニウス数」. INTEGERS: The Electronic Journal of Combinatorial Number Theory . 8 (1): A33 . 2010年1月4日閲覧。
18. トリパティ、アミタブハ（2008年）「幾何級数におけるフロベニウス問題について、論文A43」INTEGERS：組合せ数論電子ジャーナル。8 （1）。
19. ピチョット, アンリ (1987). 「Math McPuzzle」. Games Magazine . 85 (4/5月): 52.
20. Wah, Anita; Picciotto, Henri (1994). 「Lesson 5.8 Building-block Numbers」（PDF） . 『代数：テーマ、ツール、概念』p. 186.
21. Weisstein, Eric W.「マクナゲット数」. MathWorld .

さらに読む

• 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

Retrieved from "https://en.wikipedia.org/w/index.php?title=Coin_problem&oldid=1323747168"