Myntproblem

Ej att förväxla med förändringsproblem .

Med endast 2 pence och 5 pence mynt kan man inte göra 3 pence, men man kan göra vilket högre heltalsbelopp som helst.

Myntproblemet (även kallat Frobeniusmyntproblemet eller Frobeniusproblemet , efter matematikern Ferdinand Frobenius ) är ett matematiskt problem som kräver det största penningbeloppet som inte kan erhållas med enbart mynt av specificerade valörer , till exempel det största beloppet som inte kan erhållas med endast mynt med 3 och 5 enheter är 7 enheter. Lösningen på detta problem för en given uppsättning myntvalörer kallas uppsättningens Frobenius-nummer . Frobenius-numret existerar så länge som uppsättningen av myntvalörer inte har någon gemensam divisor som är större än 1.

Det finns en explicit formel för Frobenius-talet när det bara finns två olika myntvalörer, $x$ och $y$ : Frobenius-talet är då $xy-xy$ . Om antalet myntvalörer är tre eller fler är ingen explicit formel känd. Men för alla fasta antal myntvalörer finns det en algoritm som beräknar Frobenius-talet i polynomtid (i logaritmerna för myntvalörerna som bildar en indata). Ingen känd algoritm är polynomtid i antalet myntvalörer, och det allmänna problemet, där antalet myntvalörer kan vara så stort som önskat, är NP-hårt .

Påstående

I matematiska termer kan problemet uttryckas:

Givet positiva heltal $a_{1},a_{2},\dots ,a_{n}$ så att gcd $(a_{1},a_{2},\dots ,a_{n})=1$ , hitta det största heltal som inte kan uttryckas som en heltalskonisk kombination av dessa tal, dvs som en summa: $k_{1}a_{1}+k_{2}a_{2}+\dots +k_{n}a_{n}$

där $k_{1},k_{2},\dots ,k_{n}$ är icke-negativa heltal.

Detta största heltal kallas Frobenius-talet för mängden $\{a_{1},a_{2},\dots ,a_{n}\}$ och betecknas vanligtvis med $g(a_{1},a_{2},\dots ,a_{n})$

Kravet att den största gemensamma divisorn (GCD) är lika med 1 är nödvändigt för att Frobenius-talet ska existera. Om GCD inte var 1, då startar vid något tal m är de enda möjliga summorna multipler av GCD; varje tal efter m som inte är delbart med GCD kan inte representeras av någon linjär kombination av tal från mängden. Till exempel, om du hade två typer av mynt värderade till 6 cent och 14 cent, skulle GCD vara lika med 2, och det skulle inte finnas något sätt att kombinera ett antal sådana mynt för att producera en summa som var ett udda tal ; dessutom de jämna talen 2, 4, 8, 10, 16 och 22 (mindre än m=24 ) inte heller bildas. Å andra sidan, närhelst GCD är lika med 1, uppsättningen heltal som inte kan uttryckas som en konisk kombination av $\{a_{1},a_{2} ,\dots ,a_{n}\}$ är avgränsad enligt Schurs sats , och därför finns Frobenius-talet.

Frobeniustal för litet n

En lösning i sluten form finns för myntproblemet endast där n = 1 eller 2. Ingen lösning i sluten form är känd för n > 2.

n = 1

Om n = 1 så är a ₁ = 1 så att alla naturliga tal kan bildas.

n = 2

Om n = 2 kan Frobenius-talet hittas från formeln $g(a_{1},a_{2})=a_ {1}a_{2}-a_{1}-a_{2}$ . Denna formel upptäcktes av James Joseph Sylvester 1882, även om den ursprungliga källan ibland felaktigt citeras som, där författaren satte sin teorem som ett rekreationsproblem (och inte uttryckligen angav formeln för Frobenius-numret). Sylvester visade också för detta fall att det finns totalt $N(a_{1},a_{2}) =(a_{1}-1)(a_{2}-1)/2$ icke-representerbara (positiva) heltal.

En annan form av ekvationen för $g(a_{1},a_{2})$ ges av Skupień i denna proposition: Om $a_ {1},a_{2}\in \mathbb {N}$ och $\gcd(a_{1},a_{2})=1$ sedan, för varje ${\displaystyle n\geq (a_{1}-1)(a_{2}-1)} ,$ det finns exakt ett par icke-negativa heltal $\rho$ och $\sigma$ så att $\sigma <a_{1}$ och $n=\rho a_{1}+ \sigma a_{2}$ .

Formeln bevisas enligt följande. Antag att vi vill konstruera talet $m\geq (a_{1}-1)(a_{2}-1)$ . Eftersom $\gcd(a_{1},a_{2})=1$ , alla heltal $m-ja_{2}$ för $j=0,1,\ldots ,a_{1}-1$ är ömsesidigt distinkta modulo $a_{1}$ . Därför finns det ett unikt värde på $j$ , säg $j=\sigma$ , och ett icke-negativt heltal $\rho$ , så att $m=\rho a_{1}+\sigma a_{2}$ : Ja, $\rho \geq 0$ eftersom $\rho a_{1}=m-\sigma a_{2}\geq (a_{1}-1)( a_{2}-1)-(a_{1}-1)a_{2}=-a_{1}+1$ .

n = 3

Formler och snabba algoritmer är kända för tre siffror, även om beräkningarna kan vara mycket tråkiga om de görs för hand.

Enklare nedre och övre gränser för Frobenius-tal för n = 3 har också bestämts. Den asymptotiska nedre gränsen på grund av Davison

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

är relativt skarp. ( $f$ här är det modifierade Frobenius-talet som är det största heltal som inte kan representeras av positiva heltals linjära kombinationer av $a_{1},a_{2},a_{3 }$ .) Jämförelse med den faktiska gränsen (definierad av det parametriska sambandet, $f(z(i))=9i^{2}+54i +79$ där ${\displaystyle z(i)=a_{1} a_{2}a_{3}=(3i+7)(3i+10)(3i^{2}+19i+29)} )$ visar att approximationen endast är 1 mindre än det sanna värdet eftersom ${\ displaystyle i\rightarrow \infty }$ . Det antas att en liknande parametrisk övre gräns (för värden på $a_{1},a_{2},a_{3}$ som är parvis-coprime och inget element kan representeras av de andra) är $f(z(i))=6i^{2}+19i+13$ där $z(i)=a_{1}a_{2}a_{3}=(3i+2)(3i +3)(6i+7)$ .

Det asymptotiska medelbeteendet för $f$ för tre variabler är också känt:

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

Wilfs gissning

1978 antog Wilf att givna coprime-heltal $a_{1}<a_{2}<...<a_{d}$ och deras Frobenius-nummer $F$ , har vi

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

där $g$ anger antalet av alla icke-representerbara positiva heltal. 2015 bevisades en asymptotisk version av detta av Moscariello och Sammartano.

Frobenius-nummer för specialset

Aritmetiska sekvenser

Det finns en enkel formel för Frobenius-talet för en uppsättning heltal i en aritmetisk sekvens . Givet heltal a , d , w med gcd( a , d ) = 1:

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

Fallet $n=2$ ovan kan uttryckas som ett specialfall av denna formel.

I händelse av att $a>w^{2}-3w+1$ , kan vi utelämna vilken delmängd som helst av elementen $a+2d,a+3d,...,a+(w-3)d,a+(w-2)d$ från vår aritmetiska sekvens och formeln för Frobenius-talet förblir densamma.

Geometriska sekvenser

Det finns också en sluten formlösning för Frobenius-talet för en mängd i en geometrisk sekvens . Givet heltal m , n , k med gcd( m , n ) = 1:

${\displaystyle g(m^{k},m^{k-1}n,m^{k-2}n^{2},\dots ,n^{k})=n^{k-1} (mn-mn)+{\frac {m^{2}(n-1)(m^{k-1}-n^{k-1})}{mn}}.} En enklare formel som också$

visar symmetri mellan variablerna är som följer. Givet positiva heltal $a,b,k$ , med $\gcd(a,b)=1,$ låt $A_{k}(a,b)=\{a^{k},a^{k-1}b,\ldots ,b ^{k}\}$ . Sedan

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

där ${\sigma }_{k}(a,b)$ anger summan av alla heltal i $A_{k}(a,b).$

Exempel

McNugget-nummer

En låda med 20 McDonald's Chicken McNuggets

Ett specialfall av myntproblemet kallas ibland även McNugget-numren . McNuggets-versionen av myntproblemet introducerades av Henri Picciotto, som placerade det som ett pussel i Games Magazine 1987, och inkluderade det i sin algebralärobok som skrevs tillsammans med Anita Wah. Picciotto tänkte på applikationen på 1980-talet när han åt middag med sin son på McDonald's och löste problemet på en servett. Ett McNugget-nummer är det totala antalet McDonald's Chicken McNuggets i valfritt antal lådor. I Storbritannien var originalkartongerna (före introduktionen av Happy Meal -stora nuggetboxar) på 6, 9 och 20 nuggets.

Enligt Schurs teorem , eftersom 6, 9 och 20 är (setwise) relativt primtal , kan vilket tillräckligt stort heltal som helst uttryckas som en (icke-negativ, heltal) linjär kombination av dessa tre. Därför finns det ett största icke-McNugget-tal, och alla heltal större än det är McNugget-tal. Varje positivt heltal är nämligen ett McNugget-tal, med det ändliga antalet undantag:

1, 2, 3, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 22, 23, 25, 28, 31, 34, 37 och 43 (sekvens A065003 i OEIS ).

Total	0	1	2	3	4	5
+0	00 0: , , 0	1: —	2: —	3: —	4: —	5: —
+6	0 6: 1 , , 0	7: —	8: —	0 9: , 1 , 0	10:-	11: —
+12	0 12: 2 , , 0	13:-	14:-	15: 1 , 1 , 0	16:-	17:-
+18	0 18: 3 , , 0	19:-	00 20: , , 1	21: 2 , 1 , 0	22: —	23:-
+24	0 24: 4 , , 0	25:-	0 26: 1 , , 1	27: 3 , 1 , 0	28:-	0 29: , 1 , 1
+30	0 30: 5 , , 0	31: —	0 32: 2 , , 1	33: 4 , 1 , 0	34:-	35: 1 , 1 , 1
+36	0 36: 6 , , 0	37:-	0 38: 3 , , 1	39: 5 , 1 , 0	00 40: , , 2	41: 2 , 1 , 1
+42	0 42: 7 , , 0	43:-	0 44: 4 , , 1	45: 6 , 1 , 0	0 46: 1 , , 2	47: 3 , 1 , 1
+48	0 48: 8 , , 0	0 49: , 1 , 2	0 50: 5 , , 1	51: 7 , 1 , 0	0 52: 2 , , 2	53: 4 , 1 , 1
+54	0 54: 9 , , 0	55: 1 , 1 , 2	0 56: 6 , , 1	57: 8 , 1 , 0	0 58: 3 , , 2	59: 5 , 1 , 1
En möjlig uppsättning kombinationer av lådor för totalt 0 till 59 nuggets. Varje triplett anger antalet lådor om 6 , 9 respektive 20 .

Det största icke-McNugget-talet är alltså 43. Det faktum att ett heltal större än 43 är ett McNugget-tal kan ses genom att betrakta följande heltalspartitioner

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

Alla större heltal kan erhållas genom att lägga till ett antal 6:or till lämplig partition ovan.

Alternativt, eftersom ${\textrm {lcm}}(9,20)=180$ och $6|180$ , lösningen kan också erhållas genom att tillämpa en formel presenterad för $n=3$ tidigare:

$g(6,9,20)={\ textrm {lcm}}(6,9)+{\textrm {lcm}}(6,20)-6-9-20=18+60-35=43$

Dessutom visar en enkel kontroll att 43 McNuggets verkligen inte kan köpas, eftersom:

1. rutor med 6 och 9 enbart kan inte bilda 43 eftersom dessa bara kan skapa multiplar av 3 (med undantag för 3 själv);
2. att inkludera en enda ruta med 20 hjälper inte, eftersom den nödvändiga återstoden (23) inte heller är en multipel av 3; och
3. mer än en låda med 20, kompletterad med lådor i storlek 6 eller större, kan uppenbarligen inte leda till totalt 43 McNuggets.

Sedan introduktionen av 4-delade Happy Meal-nugget-lådorna är det största antalet icke-McNugget 11. I länder där 9-delarnas storlek ersätts med 10-delarnas storlek, finns det inget största icke-McNugget-numret, eftersom ett udda tal inte kan göras.

Andra exempel

I rugby union finns det fyra typer av poäng: straffmål (3 poäng), droppmål (3 poäng), försök (5 poäng) och omvandlat försök (7 poäng). Genom att kombinera dessa är valfri poängsumma möjlig utom 1, 2 eller 4. I rugbysjuor , även om alla fyra typer av poäng är tillåtna, är försök till straffmål sällsynta och släppmål nästan okända. Detta innebär att lagets poäng nästan alltid består av multiplar av försök (5 poäng) och omvandlat försök (7 poäng). Följande poäng (utöver 1, 2 och 4) kan inte göras från multiplar av 5 och 7 och ses därför nästan aldrig i sjuor: 3, 6, 8, 9, 11, 13, 16, 18 och 23. Till exempel, inga av dessa poäng registrerades i någon match i 2014-15 Sevens World Series .

På samma sätt, i amerikansk fotboll , är det enda sättet för ett lag att få exakt en poäng om en säkerhet tilldelas mot motståndarlaget när de försöker konvertera efter en touchdown. Eftersom 2 poäng delas ut för safeties från vanligt spel, och 3 poäng delas ut för field goals , alla andra poäng än 1–0, 1–1, 2–1, 3–1, 4–1, 5–1 och 7– 1 är möjliga.

Ansökningar

Shellsort Tidskomplexitet

Shellsort - algoritmen är en sorteringsalgoritm vars tidskomplexitet för närvarande är ett öppet problem . Komplexiteten i värsta fall har en övre gräns som kan ges i termer av Frobenius-talet för en given sekvens av positiva heltal.

Minsta problem med levande vikt

Petri-nät är användbara för att modellera problem i distribuerad datoranvändning . För specifika typer av petri-nät, nämligen konservativt viktade kretsar, skulle man vilja veta vilka möjliga "tillstånd" eller "markeringar" med en given vikt som är "live". Problemet med att bestämma den lägsta levande vikten motsvarar Frobenius-problemet.

Termer i utökad effekt av ett polynom

När ett univariat polynom höjs till någon makt kan man behandla polynomets exponenter som en uppsättning heltal. Det expanderade polynomet kommer att innehålla potenser av $x$ större än Frobenius-talet för någon exponent (när GCD=1), t.ex. för $(1+x^{6) }+x^{7})^{n}$ mängden är {6, 7} som har ett Frobenius-tal på 29, så en term med $x^{29}$ kommer aldrig att visas för något värde av $n$ men något värde på $n$ kommer att ge termer som har någon potens av $x$ större än 29. När exponenternas GCD inte är 1 så kommer potenser större än något värde att visas endast om de är en multipel av GCD, t.ex. för $(1+x^{9}+x^{15})^{n}$ , 24 potenser , 27, ... visas för vissa värden på $n$ men aldrig värden större än 24 som inte är multiplar av 3 (eller de mindre värdena 1-8, 10-14, 16, 17 19-23).

Se även

• Frimärksproblem
• Förändringsproblem
• Silvermynt
• Numerisk halvgrupp

externa länkar

• Så här beställer du 43 Chicken McNuggets – Numberphile