フロベニウスの硬貨交換問題のソースを表示

{{要改訳|date=2019-01-31}}
[[画像:Two Pence 01.jpg|140px|thumb|2ペンスと5ペンスのコインだけでは、3ペンスを作ることはできないが、4ペンス以上は全て作ることができる。]]
'''フロベニウスの硬貨交換問題'''（フロベニウスのこうかこうかんもんだい）とは、指定された種類の[[硬貨]]だけではぴったり払えない最大の金額を求める[[数学]]の問題である<ref name="ramirez">{{Cite book |author=J. Ramírez Alfonsín |title=The Diophantine Frobenius problem |publisher=Oxford Univ. Press |year=2005}}</ref>。'''フロベニウスの問題'''、'''シルベスターの切手問題'''とも呼ばれる。数学者[[フェルディナント・ゲオルク・フロベニウス]]に因んで名付けられた。例えば、3円と5円の硬貨だけでは作れない最大の金額は7円である。コインの種類の組み合わせに対するこの問題の解は'''フロベニウス数'''と呼ばれる。フロベニウス数が存在するのは、硬貨の額面が[[互いに素 (整数論)|互いに素]]のときに限られる。

硬貨が {{mvar|a}}円と {{mvar|b}}円の2種類だけの場合は、フロベニウス数の公式が存在し、{{math2|1=''ab'' &minus; ''a'' &minus; ''b'' (= (''a'' &minus; 1)(''b'' &minus; 1) &minus; 1)}} である。硬貨が3種類以上の場合の公式は未解決問題である。しかし、任意の種類の硬貨に対して、（硬貨の種類の数の「対数」に対して）[[多項式時間]]でフロベニウス数を計算する[[アルゴリズム]]が存在する<ref name="kannan">{{Cite journal |author=Ravi Kannan |year=1992 |title=Lattice translates of a polytope and the Frobenius problem |journal=Combinatorica |volume=12 |issue=2 |pages=161-177 |doi=10.1007/BF01204720}}</ref>。硬貨の種類に対して多項式時間で解けるアルゴリズムは見つかっておらず、硬貨の種類に制限を設けない一般的な問題は[[NP困難]]である<ref name="beidhoffer">{{Cite journal |last=D. Beihoffer|last2=J. Hendry |last3=A. Nijenhuis |last4=S. Wagon |year=2005 |title=Faster algorithms for Frobenius numbers |url=http://www.combinatorics.org/Volume_12/Abstracts/v12i1r27.html |journal=Electronic Journal of Combinatorics |volume=12 |page=R27}}</ref><ref name="mw">{{MathWorld}}</ref>。

== 命題 ==
数学的には、問題は次のように定式化される。
: [[互いに素 (整数論)|互いに素]]（すなわち {{math2|1=[[最大公約数|gcd]] (''a''{{sub|1}}, ''a''{{sub|2}}, …, ''a{{sub|n}}'') = 1}}）である正の[[整数]] {{math2|''a''{{sub|1}}, ''a''{{sub|2}}, …, ''a{{sub|n}}''}} が与えられたとき、これらの数の整数の[[錐結合|和]]（錐結合）、つまり
:: {{math2|''k''{{sub|1}}''a''{{sub|1}} + ''k''{{sub|2}}''a''{{sub|2}} + … + ''k{{sub|n}}a{{sub|n}}''}} 
: で表現できない最大の整数を求めよ。ここで係数 {{math2|''k''{{sub|1}}, ''k''{{sub|2}}, …, ''k{{sub|n}}''}} は非負整数とする。

この最大の整数を集合 {{math2|{{mset|''a''{{sub|1}}, ''a''{{sub|2}}, …, ''a{{sub|n}}''}}}} の'''フロベニウス数'''と呼び、{{math2|''g''(''a''{{sub|1}}, ''a''{{sub|2}}, …, ''a{{sub|n}}'')}} で表される。

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

== 小さい''n''に対するフロベニウス数 ==
コインの種類 ''n'' が 1 または 2 の場合のフロベニウス数は閉形式を持つことが知られている。''n'' が 2 より大きい場合に対する閉形式での解は知られていない<ref>{{MathWorld|title=Coin Problem}}</ref>。

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

=== ''n'' = 2 ===
''n'' = 2 ならば、フロベニウス数は <math>g(a_1, a_2)=a_1a_2-a_1-a_2</math> である。この式は、[[ジェームス・ジョセフ・シルベスター]]が1882年に発見した<ref>{{Cite journal|last=Sylvester, James Joseph |year=1882 |title=On subinvariants, i.e. Semi-Invariants to Binary Quantics of an Unlimited Order |journal=American Journal of Mathematics |volume=5 |page=134 |jstor=2369536}}</ref>。時に、別の文献<ref>{{Cite journal |author=Sylvester, James Joseph |year=1884 |title=Question 7382 |url=https://archive.org/stream/mathematicalque05unkngoog#page/n150 |journal=Mathematical Questions from the Educational Times |volume=41 |page=21}}</ref>が誤ってこの定理の初出とされることがある<!--つまり、出典[7]は「原本は時々誤って引用されている」という数学史的な記述を裏付ける文献ではなく、誤って引用される文献そのものだと考える。出典[7]は確認したが、確かにシルベスターが書いた数論の問題であった。英語版原文でこの部分が書き込まれたとき [https://en.wikipedia.org/w/index.php?title=Coin_problem&diff=prev&oldid=823662483]、現在とはカンマの位置が異なり「 although the original source is sometimes incorrectly cited as [7],」のように書かれていた。著者の意図としては文献番号[7]も文章の一部だったと思われる。そうだとすれば、文法上は新しく書き換えた訳文のように解釈するのが正しい。-->。この文献でシルベスターは、自らの定理をレクリエーション数学の問題として出した<ref>{{Cite book |last=J. Ramírez Alfonsín|title=The Diophantine Frobenius problem |year=2005 |publisher=Oxford Univ. Press |page=xiii}}</ref>（ただし、フロベニウス数の公式とは明示しなかった）。またそこで、この場合に<math>N(a_1,a_2)=\frac{(a_1-1)(a_2-1)}{2}</math> 個の表せない自然数が存在することも述べている（シルベスターの閉形式定理）。<!--ここまでが出典[7]の内容の説明。-->

Skupieńは、フロベニウス数に対して別の形の公式を与えた<ref>{{Cite journal |last=Skupień |first=Zdzisław |authorlink=Zdzisław Skupień |year=1993 |title=A generalization of Sylvester’s and Frobenius’ problems |url=http://matwbn.icm.edu.pl/ksiazki/aa/aa65/aa6545.pdf|journal=Acta Arithmetica |volume=LXV.4 |pages=353-366}}</ref>。Skupieńは、「最大公約数が1である2個の自然数 ''a''{{sub|1}} と ''a''{{sub|2}} がある場合、<math>(a_1-1)(a_2-1)</math> 以上の任意の自然数 mに対して、非負整数の ''ρ'' と ''σ'' を用いて、<math>m=\rho a_1+\sigma a_2</math>（ただし<math>\sigma < a_1</math>）という表現が可能である。」という形式で述べた。

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

<math>m\geq(a_1-1)(a_2-1)</math> を表現したいとする。{{math2|''a''{{sub|1}}, ''a''{{sub|2}}}} の最大公約数は1であるため、<math>\sigma = 0, 1, \cdots, a_1 - 1</math> に対して <math>m - \sigma a_2</math> はすべて ''a''{{sub|1}} を法として互いに異なる。したがって、<math>m = \rho a_1 + \sigma a_2</math> となるようなただ一つの ''σ'' と、非負整数 ''ρ'' が存在する。''ρ'' が非負であるのは、
:<math>\rho a_1 = m-\sigma a_2 \geq(a_1-1)(a_2-1)-(a_1-1)a_2 = -a_1+1</math>
から分かる。

=== ''n'' = 3 ===
''n'' = 3 に対するフロベニウス数を求める高速なアルゴリズムは知られている（数値半群を参照）。しかし、手作業での計算は非常に面倒である。また、''n'' = 3 のフロベニウス数に対する下限および上限はすでに得られている。Davisonによって与えられたフロベニウス数の下限は
:<math>g(a_1 , a_2, a_3)\geq\sqrt{3a_1 a_2 a_3}-a_1 -a_2 -a_3</math>
であることが知られている<ref>{{Cite journal |last=M. Beck |last2=S. Zacks |year=2004 |title=Refined upper bounds for the linear Diophantine problem of Frobenius |journal=Adv. Appl. Math. |volume=32 |issue=3 |pages=454-467 |arxiv=math/0305420 |doi=10.1016/S0196-8858(03)00055-1}}</ref>。

また、平均は
: <math>g(a_1, a_2, a_3 )+ a_1 +a_2 +a_3 \sim\frac{8}{\pi} \sqrt{a_1 a_2 a_3}</math>
に漸近することが知られている<ref>{{Cite journal |last=A. Ustinov |year=2009 |title=The solution of Arnold's problem on the weak asymptotics of Frobenius numbers with three arguments |url=https://iopscience.iop.org/1064-5616/200/4/A07 |journal=Sbornik: Mathematics |volume=200 |issue=4 |pages=131-160 |bibcode=2009SbMat.200..597U |doi=10.1070/SM2009v200n04ABEH004011}}</ref>。また、この左辺は修正フロベニウス数と呼ばれる、'''正の'''整数の線形和で表現できない最大の整数である。

== 特殊な集合に対するフロベニウス数 ==
=== 等差数列 ===
[[等差数列]]を要素とする整数の集合のフロベニウス数は簡単に求められる<ref>{{Cite book |last=Ramirez Alfonsin |first=Jorge |title=The Diophantine Frobenius Problem |year=2005 |publisher=Oxford University Press |pages=59-60}}</ref>。いずれも整数の初項 ''a''、等差 ''d''、 ''s'' に対して、''a'' と ''d'' の最大公約数が1であれば、 
: <math>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</math>
であり、前述の ''n'' = 2 の場合は、上式で ''d'' = ''a''{{sub|2}} &minus; ''a''{{sub|1}}, ''s'' = 1 とした特殊な場合に対応する。

=== 等比数列 ===
[[等比数列]]を要素とする整数の集合のフロベニウス数の閉形式での解も存在する<ref>{{Cite journal |last=Ong, Darren C. |last2=Ponomarenko, Vadim |year=2008 |title=The Frobenius Number of Geometric Sequences |url=http://www.emis.ams.org/journals/INTEGERS/papers/i33/i33.Abstract.html |journal=INTEGERS: the Electronic Journal of Combinatorial Number Theory |volume=8 |issue=1 |page=A33}}</ref>。いずれも整数の''a'', ''b'', ''k'' に対して、''a'' と ''b'' の最大公約数が1であれば、その要素は <math>a^k, a^{k-1}b, a^{k-2}b^2, \cdots a^2b^{k-2}, ab^{k-1},b^k</math> という対称な形となり、
:<math>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}</math>
である<ref>{{Cite journal |last=Tripathi |first=Amitabha |year=2008 |title=On the Frobenius Problem for Geometric Sequences, Article A43 |journal=Integers: the Electronic Journal of Combinatorial Number Theory |volume=8 |issue=1}}</ref>。

また、<math>\sigma_k(a,b) = a^k+a^{k-1}b+\cdots+ab^{k-1}+b^k</math>とすると、<math>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})</math>と簡潔に表せる<ref>{{Cite journal |title=On the Frobenius Problem for Geometric Sequences, Article A43 |last=Tripathi |first=Amitabha |journal=Integers: the Electronic Journal of Combinatorial Number Theory |volume=8 |issue=1 |year=2008}}</ref>。

== 例 ==
=== チキンマックナゲット数 ===
[[画像:Chicken McNuggets.jpg|thumb|20個入りの、[[チキンマックナゲット]]]]
有名な特別な場合に、'''チキンマックナゲット数'''がある。この問題はHenri PicciottoがAnita Wahと共著で代数の教科書に書いたことで導入された<ref>{{Cite book |last=Wah |first=Anita |title=Algebra: Themes, Tools, Concepts |url=http://www.mathedpage.org/attc/lessons/ch.05/5.08-building-blocks.pdf |year=1994 |page=186 |chapter=Lesson 5.8 Building-block Numbers |last2=Picciotto |first2=Henri}}</ref>。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
（{{OEIS|id=A065003}}）
{|class="wikitable" style="float:right;clear:right;margin-left:1ex;font-size:90%"
!style="padding:0"|Total
!0!!1!!2!!3!!4!!5
|-
!+0
|bgcolor="#ccffff"|&#x2007;0:0,0,{{Red-text|0}}
|bgcolor="white"|&#x2007;1:&#x2014;
|bgcolor="white"|&#x2007;2:&#x2014;
|bgcolor="white"|&#x2007;3:&#x2014;
|bgcolor="white"|&#x2007;4:&#x2014;
|bgcolor="white"|&#x2007;5:&#x2014;
|-
!+6
|bgcolor="#ccffff"|&#x2007;6:1,0,{{Red-text|0}}
|bgcolor="white"|&#x2007;7:&#x2014;
|bgcolor="white"|&#x2007;8:&#x2014;
|bgcolor="#ccccff"|&#x2007;9:0,1,{{Red-text|0}}
|bgcolor="white"|10:&#x2014;
|bgcolor="white"|11:&#x2014;
|-
!+12
|bgcolor="#ccffff"|12:2,0,{{Red-text|0}}
|bgcolor="white"|13:&#x2014;
|bgcolor="white"|14:&#x2014;
|bgcolor="#ccccff"|15:1,1,{{Red-text|0}}
|bgcolor="white"|16:&#x2014;
|bgcolor="white"|17:&#x2014;
|-style="border-top:2px dotted"
!+18
|bgcolor="#ccffff"|18:3,0,{{Red-text|0}}
|bgcolor="white"|19:&#x2014;
|bgcolor="#ccffcc"|20:0,0,{{Red-text|1}}
|bgcolor="#ccccff"|21:2,1,{{Red-text|0}}
|bgcolor="white"|22:&#x2014;
|bgcolor="white"|23:&#x2014;
|-
!+24
|bgcolor="#ccffff"|24:4,0,{{Red-text|0}}
|bgcolor="white"|25: &#x2014;
|bgcolor="#ccffcc"|26:1,0,{{Red-text|1}}
|bgcolor="#ccccff"|27:3,1,{{Red-text|0}}
|bgcolor="white"|28: &#x2014;
|bgcolor="#99cc99"|29:0,1,{{Red-text|1}}
|-
!+30
|bgcolor="#ccffff"|30:5,0,{{Red-text|0}}
|bgcolor="white"|31: &#x2014;
|bgcolor="#ccffcc"|32:2,0,{{Red-text|1}}
|bgcolor="#ccccff"|33:4,1,{{Red-text|0}}
|bgcolor="white"|34: &#x2014;
|bgcolor="#99cc99"|35:1,1,{{Red-text|1}}
|-style="border-top:2px dotted"
!+36
|bgcolor="#ccffff"|36:6,0,{{Red-text|0}}
|bgcolor="white"|37: &#x2014;
|bgcolor="#ccffcc"|38:3,0,{{Red-text|1}}
|bgcolor="#ccccff"|39:5,1,{{Red-text|0}}
|bgcolor="#ffff99"|40:0,0,{{Red-text|2}}
|bgcolor="#99cc99"|41:2,1,{{Red-text|1}}
|-
!+42
|bgcolor="#ccffff"|42:7,0,{{Red-text|0}}
|bgcolor="white" style="border:solid"|43: &#x2014;
|bgcolor="#ccffcc"|44:4,0,{{Red-text|1}}
|bgcolor="#ccccff"|45:6,1,{{Red-text|0}}
|bgcolor="#ffff99"|46:1,0,{{Red-text|2}}
|bgcolor="#99cc99"|47:3,1,{{Red-text|1}}
|-
!+48
|bgcolor="#ccffff"|48:8,0,{{Red-text|0}}
|bgcolor="#ffcc99"|49:0,1,{{Red-text|2}}
|bgcolor="#ccffcc"|50:5,0,{{Red-text|1}}
|bgcolor="#ccccff"|51:7,1,{{Red-text|0}}
|bgcolor="#ffff99"|52:2,0,{{Red-text|2}}
|bgcolor="#99cc99"|53:4,1,{{Red-text|1}}
|-
!+54
|bgcolor="#ccffff"|54:9,0,{{Red-text|0}}
|bgcolor="#ffcc99"|55:1,1,{{Red-text|2}}
|bgcolor="#ccffcc"|56:6,0,{{Red-text|1}}
|bgcolor="#ccccff"|57:8,1,{{Red-text|0}}
|bgcolor="#ffff99"|58:3,0,{{Red-text|2}}
|bgcolor="#99cc99"|59:5,1,{{Red-text|1}}
|-
|colspan="7"|0から59個に対する、チキンマックナゲットの買い方。<br />コロンの右の3個の数は、それぞれ '''6''', '''9,''' '''{{Red-text|20}}'''個のセットを買う数。
|}
上記の表より、最大の非チキンマックナゲット数は43である<ref>{{MathWorld|urlname=McNuggetNumber|title=McNugget Number}}</ref>。43より大きい任意の整数がチキンマックナゲット数であることは、以下の[[自然数の分割]]のいずれかに6を適当な回数だけ足し合わせることで確かめられる。
: <math>\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}</math>
さらに、以下のように、43個ちょうどのチキンマックナゲットは購入できないことが示される。
# 6個入と9個入のセットだけでは、3の倍数個しか購入できない（3個は不可能）ため、43個を購入できない。
# 20個入を1セット購入すると、残りの23個が3の倍数ではないため、20個入のセットを1個だけ含めても43個を購入できない。
# 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のどの試合でも記録されていない。

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

== 参考文献 ==
{{Reflist}}

== 関連項目 ==
* [[切手問題]] - 限られた枚数の切手で表せない最小の整数
* {{仮リンク|シルバーコインゲーム|en|Sylver coinage}}<!--
* [[釣銭最適化問題]]
* [[数値半群]]-->

== 外部リンク ==
* {{高校数学の美しい物語|987|フロベニウスの硬貨交換問題}}
* {{YouTube|vNTSugyS038|How to order 43 Chicken McNuggets – Numberphile}}

{{DEFAULTSORT:ふろへにうすのこうかこうかんもんたい}}
[[Category:数学パズル]]
[[Category:数論]]
[[Category:未査読の翻訳があるページ]]
[[Category:数学に関する記事]]