Problem z monetą

Mając tylko 2 pensy i 5 pensów, nie można zarobić 3 pensów, ale można uzyskać dowolną wyższą liczbę całkowitą.

Problem z monetą (nazywany również problemem z monetą Frobeniusa lub problemem Frobeniusa , na cześć matematyka Ferdynanda Frobeniusa ) jest problemem matematycznym , który wymaga największej kwoty pieniężnej, której nie można uzyskać przy użyciu tylko monet o określonych nominałach , na przykład największa kwota której nie można uzyskać przy użyciu tylko monet o wartości 3 i 5 jednostek, wynosi 7 jednostek. Rozwiązanie tego problemu dla danego zestawu nominałów monet nazywa się liczbą Frobeniusa tego zestawu. Liczba Frobeniusa istnieje, dopóki zbiór nominałów monet nie ma wspólnego dzielnika większego niż 1.

Istnieje wyraźny wzór na liczbę Frobeniusa, gdy istnieją tylko dwa różne nominały monet i ${\ Displaystyle$ $y}$ : liczba Frobeniusa wynosi wtedy ${\ displaystyle xy-xy$ . Jeśli liczba nominałów monet wynosi trzy lub więcej, nie jest znany żaden wyraźny wzór. Jednak dla dowolnej ustalonej liczby nominałów monet istnieje algorytm obliczający liczbę Frobeniusa w czasie wielomianowym (w logarytmach nominałów monet tworzących dane wejściowe). Żaden znany algorytm nie jest czasem wielomianowym w liczbie nominałów monet, a ogólny problem, w którym liczba nominałów monet może być tak duża, jak jest to pożądane, jest NP-trudny .

Oświadczenie

W kategoriach matematycznych problem można określić:

Biorąc pod uwagę dodatnie liczby całkowite takie, że gcd

{\ Displaystyle (a_ {1}, a_ {2}, \ kropki, a_ {n}) = 1

{\ Displaystyle a_ {1}, a_

, znajdź największą liczbę całkowitą, której nie można wyrazić jako całkowitą stożkową kombinację tych liczb, tj. Jako sumę:

{\ Displaystyle k_ {1} a_ {1} + k_ {2} a_ {2} + \ kropki + k_ {n} a_ {n}}

gdzie

{\ Displaystyle k_ {1}, k_ {2}, \ kropki, k_ {n}}

są nieujemnymi liczbami całkowitymi.

Ta największa liczba całkowita nazywana jest liczbą Frobeniusa zbioru ${\ Displaystyle \ {a_ {1}, a_ {2}, \ kropki, a_ {n} \}}$ i sol ${\ Displaystyle g (a_ {1}, a_ {2}, \ kropki, a_ {n})$

Wymóg, aby największy wspólny dzielnik (NWD) był równy 1, jest konieczny, aby istniała liczba Frobeniusa. Gdyby GCD nie wynosił 1, to zaczynając od pewnej liczby m jedyne możliwe sumy to wielokrotności NWD; każda liczba powyżej m , która nie jest podzielna przez NWD, nie może być reprezentowana przez żadną liniową kombinację liczb ze zbioru. Na przykład, gdybyś miał dwa rodzaje monet o wartości 6 centów i 14 centów, NWD równałoby się 2 i nie byłoby możliwości połączenia dowolnej liczby takich monet w celu uzyskania sumy, która byłaby liczbą nieparzystą ; dodatkowo nie mogły powstać również liczby parzyste 2, 4, 8, 10, 16 i 22 (mniejsze niż m=24 ). Z drugiej strony, ilekroć GCD równa się 1, zbiór liczb całkowitych, których nie można wyrazić jako stożkowej kombinacji $\ Displaystyle \ {a_ {1}, a_ {2} ,\kropki ,a_{n}\}}$ jest ograniczone zgodnie z twierdzeniem Schura , a zatem liczba Frobeniusa istnieje.

Liczby Frobeniusa dla małych n

Rozwiązanie w postaci zamkniętej istnieje dla problemu monety tylko wtedy, gdy n = 1 lub 2. Żadne rozwiązanie w postaci zamkniętej nie jest znane dla n > 2.

n = 1

Jeśli n = 1, to a ₁ = 1, więc można utworzyć wszystkie liczby naturalne.

n = 2

Jeśli n = 2, liczbę Frobeniusa można znaleźć ze wzoru sol $\ Displaystyle g (a_ {1}, a_ {2}) = a_ {1}a_{2}-a_{1}-a_{2}}$ . Formuła ta została odkryta przez Jamesa Josepha Sylvestera w 1882 r., Chociaż oryginalne źródło jest czasami błędnie cytowane jako, w którym autor umieścił swoje twierdzenie jako problem rekreacyjny (i nie podał wprost wzoru na liczbę Frobeniusa). Sylvester wykazał również w tym przypadku, że w sumie istnieje ${\ Displaystyle N (a_ {1}, a_ {2}) =(a_{1}-1)(a_{2}-1)/2}$ niereprezentowalne (dodatnie) liczby całkowite.

Inną postać równania na $\ Displaystyle g (a_ {1}, a_ {2})}$ podaje Skupień w tym twierdzeniu: Jeśli ${\ Displaystyle a_ {1}, a_ {2} \ in \ mathbb {N}}$ i ${\ Displaystyle \ gcd (a_ {1}, a_ {2}) = 1}$ wtedy dla każdego $\ Displaystyle n \ geq (a_ {1} -1) (a_ {2} -1)}$ , jest dokładnie jedna para nieujemnych liczb całkowitych $rho}$ ${\ Displaystyle$ $\sigma a_{2}}$ i $\ sigma}$ $Displaystyle$ takie, że i $Displaystyle n = \ rho a_$ .

Formuła jest udowodniona w następujący sposób. Załóżmy, że chcemy skonstruować liczbę ${\ Displaystyle m \ geq (a_ {1} -1) (a_ {2} -1)}$ . Ponieważ ${\ Displaystyle \ gcd (a_ {1}, a_ {2}) = 1$ , wszystkie liczby całkowite ${\ Displaystyle m-ja_ {2}}$ dla ${\ Displaystyle j = 0, 1, \ ldots, a_ {1} -1}$ są wzajemnie różne modulo ${\ Displaystyle a_ {1}}$ . ${\ Displaystyle m = \ rho a_ {1} + \ sigma a_ {2}}$ istnieje unikalna wartość , $za$ liczba całkowita $taka$ , $że$ : Rzeczywiście, ${\ Displaystyle \ rho \ geq 0},$ ponieważ ${\ Displaystyle \ rho a_ {1} = m- \ sigma a_ {2} \ geq (a_ {1} -1) ( a_{2}-1)-(a_{1}-1)a_{2}=-a_{1}+1}$ .

n = 3

Formuły i szybkie algorytmy są znane z trzech liczb, chociaż obliczenia wykonywane ręcznie mogą być bardzo uciążliwe.

Wyznaczono również prostsze dolne i górne granice liczb Frobeniusa dla n = 3. Asymptotyczna dolna granica ze względu na Davisona

{\ Displaystyle f (a_ {1}, a_{2},a_{3})\równoważnik g(a_{1},a_{2},a_{3})+a_{1}+a_{2}+a_{3}\geq {\sqrt { 3a_{1}a_{2}a_{3}}}}

jest stosunkowo ostry. ( tutaj jest $zmodyfikowana$ liczba Frobeniusa , która jest największą liczbą całkowitą, której nie można przedstawić za pomocą dodatnich liczb całkowitych $\ Displaystyle a_ {1}, a_ {2}, a_ {3 }}$ kombinacji za .) Porównanie z rzeczywistą granicą (zdefiniowaną przez relację parametryczną, ${\ Displaystyle f (z (i)) = 9i ^ {2} + 54i +79}$ gdzie ${\ Displaystyle z (i) = a_ {1} a_{2}a_{3}=(3i+7)(3i+10)(3i^{2}+19i+29)} )$ pokazuje, że przybliżenie jest tylko o 1 mniejsze od prawdziwej wartości, ponieważ ${\ styl wyświetlania i\rightarrow \infty }$ . Przypuszcza się, że podobna parametryczna górna granica (dla wartości, które $nie$ jest reprezentowany inne) to ${\ Displaystyle f (z (i)) = 6i ^ {2} + 19i + 13}$ gdzie ${\ Displaystyle Z (i) = a_ {1} a_ {2} a_ {3} = (3i + 2) (3i +3)(6i+7)}$ .

asymptotyczne średnie zachowanie dla trzech zmiennych: ${\ displaystyle f}$

{\ Displaystyle f (a_ {1}, a_ {2}, a_ {3}) \ sim {\ Frac {8} \pi }}{\sqrt {a_{1}a_{2}a_{3}}},}

Przypuszczenie Wilfa

W 1978 Wilf przypuszczał, że dane liczby całkowite względnie pierwsze ${\ displaystyle a_ {1}<a_ {2}<... <a_ {d}}$ i ich liczba Frobeniusa mamy ${\ displaystyle F}$

{\ Displaystyle d \ geq {\ Frac {F + 1} {F + 1-g}}}

gdzie oznacza liczbę wszystkich dodatnich liczb całkowitych, których nie można $.$ W 2015 roku asymptotyczna wersja tego została udowodniona przez Moscariello i Sammartano.

Liczby Frobeniusa do zestawów specjalnych

Ciągi arytmetyczne

Istnieje prosty wzór na liczbę Frobeniusa zbioru liczb całkowitych w ciągu arytmetycznym . Biorąc pod uwagę liczby całkowite a , d , w gdzie gcd( a , d ) = 1:

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

$.$ przypadek wyrazić jako szczególny przypadek tego

$_$ przypadku $_$ elementów _ nasz ciąg arytmetyczny i wzór na liczbę Frobeniusa pozostają takie same.

Sekwencje geometryczne

Istnieje również rozwiązanie w postaci zamkniętej dla liczby Frobeniusa zbioru w ciągu geometrycznym . Dane liczby całkowite m , n , k gdzie gcd( m , n ) = 1:

{\ Displaystyle g (m ^ {k}, m ^ {k-1} n, m ^ {k-2} n ^ {2}, \ kropki, n ^ {k}) = n ^ {k-1} (mn-mn)+{\frac {m^{2}(n-1)(m^{k-1}-n^{k-1})}{mn}}.} Prostsza formuła, która również

wyświetla symetria między zmiennymi jest następująca. Biorąc pod uwagę dodatnie liczby całkowite

{\ Displaystyle a, b, k}

, z

{\ Displaystyle \ gcd (a, b) = 1,}

niech

{\ Displaystyle A_ {k} (a, b) = \ {a ^ {k}, a ^ {k-1} b, \ ldots, b ^{k}\}}

. Wtedy

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

gdzie

{\ Displaystyle {\ sigma} _ {k} (a, b)}

oznacza sumę wszystkich liczb całkowitych w

{\ Displaystyle A_ {k} (a, b).}

Przykłady

Liczby McNuggeta

Pudełko 20 McDonald's Chicken McNuggets

Jeden szczególny przypadek problemu z monetą jest czasami określany jako liczby McNuggeta . Wersja McNuggets problemu z monetą została przedstawiona przez Henri Picciotto, który umieścił ją jako układankę w Games Magazine w 1987 roku i umieścił ją w swoim podręczniku do algebry, którego współautorem jest Anitą Wah. Picciotto pomyślał o aplikacji w latach 80., jedząc z synem obiad w McDonald's, rozwiązując problem na serwetce. Liczba McNugget to całkowita liczba McNuggetów z kurczaka McDonald's w dowolnej liczbie pudełek. W Wielkiej Brytanii oryginalne pudełka (przed wprowadzeniem pudełek samorodków wielkości Happy Meal ) zawierały 6, 9 i 20 samorodków.

Zgodnie z twierdzeniem Schura , ponieważ 6, 9 i 20 są (zbiorowo) względnie pierwsze , każdą wystarczająco dużą liczbę całkowitą można wyrazić jako (nieujemną, całkowitą) kombinację liniową tych trzech. Dlatego istnieje największa liczba inna niż McNugget, a wszystkie liczby całkowite większe od niej są liczbami McNugget. Mianowicie, każda dodatnia liczba całkowita jest liczbą McNuggeta ze skończoną liczbą wyjątków:

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

Całkowity	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
Możliwy zestaw kombinacji pudełek dla łącznie od 0 do 59 samorodków. Każda trójka oznacza odpowiednio liczbę pudełek 6 , 9 i 20 .

Zatem największą liczbą inną niż McNugget jest 43. Fakt, że każda liczba całkowita większa niż 43 jest liczbą McNugget, można zobaczyć, rozważając następujące partycje liczb całkowitych

{\ Displaystyle 44 = 6 + 9 + 9 + 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}

Dowolną większą liczbę całkowitą można uzyskać, dodając pewną liczbę 6 do odpowiedniego podziału powyżej.

Alternatywnie, ponieważ ${\ Displaystyle {\ textrm {lcm}} (9,20) = 180}$ i ${\ Displaystyle 6|180}$ , rozwiązanie można również uzyskać, stosując wzór przedstawiony dla ${\ Displaystyle n = 3}$ wcześniej: ^{[ wątpliwe - omówić ]}

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

Ponadto proste sprawdzenie pokazuje, że 43 McNuggets rzeczywiście nie można kupić, ponieważ:

same pola 6 i 9 nie mogą tworzyć 43, ponieważ mogą one tworzyć tylko wielokrotności 3 (z wyjątkiem samej 3);
uwzględnienie pojedynczego pola 20 nie pomaga, ponieważ wymagana reszta (23) również nie jest wielokrotnością 3; I
więcej niż jedno pudełko po 20, uzupełnione pudełkami o rozmiarze 6 lub większym, oczywiście nie może dać w sumie 43 McNuggets.

Od czasu wprowadzenia 4-częściowych pudełek Happy Meal w rozmiarze samorodków największa liczba inna niż McNugget to 11. W krajach, w których rozmiar 9-częściowy jest zastępowany rozmiarem 10-częściowym, nie ma największej liczby innej niż McNugget, ponieważ nie można utworzyć żadnej liczby nieparzystej.

Inne przykłady

W rugby istnieją cztery rodzaje punktacji: bramka karna (3 punkty), bramka z rzutu karnego (3 punkty), podwyższenie (5 punktów) i przeliczone podwyższenie (7 punktów). Łącząc je, możliwa jest dowolna suma punktów z wyjątkiem 1, 2 lub 4. W siódemkach rugby , chociaż dozwolone są wszystkie cztery rodzaje wyników, próby zdobycia bramek karnych są rzadkie, a stracone bramki są prawie nieznane. Oznacza to, że wyniki zespołu prawie zawsze składają się z wielokrotności przyłożenia (5 punktów) i przeliczonego przyłożenia (7 punktów). Następujące wyniki (oprócz 1, 2 i 4) nie mogą być utworzone z wielokrotności 5 i 7, dlatego prawie nigdy nie występują w siódemkach: 3, 6, 8, 9, 11, 13, 16, 18 i 23. Dla przykładu, żaden z tych wyników nie został odnotowany w żadnym meczu w ramach Sevens World Series 2014-15 .

Podobnie w futbolu amerykańskim jedynym sposobem, aby drużyna zdobyła dokładnie jeden punkt, jest przyznanie bezpieczeństwa drużynie przeciwnej, gdy ta próbuje zmienić wynik po przyłożeniu. Ponieważ 2 punkty są przyznawane za asekuracje z normalnej gry, a 3 punkty są przyznawane za rzuty z gry , wszystkie wyniki inne niż 1–0, 1–1, 2–1, 3–1, 4–1, 5–1 i 7– 1 są możliwe.

Aplikacje

Złożoność czasowa sortowania Shella

Algorytm Shellsort jest algorytmem sortującym, którego złożoność czasowa jest obecnie problemem otwartym . Złożoność najgorszego przypadku ma górną granicę, którą można podać w postaci liczby Frobeniusa danej sekwencji dodatnich liczb całkowitych.

Najmniejszy problem z żywą wagą

Sieci Petriego są przydatne do modelowania problemów w obliczeniach rozproszonych . W przypadku określonych rodzajów sieci Petriego, a mianowicie konserwatywnych obwodów ważonych, chciałoby się wiedzieć, jakie możliwe „stany” lub „oznaczenia” o danej wadze są „na żywo”. Problem określenia najmniejszej żywej wagi jest równoważny problemowi Frobeniusa.

Terminy w rozszerzonej potędze wielomianu

Kiedy wielomian jednowymiarowy jest podniesiony do pewnej potęgi, wykładniki wielomianu można traktować jako zbiór liczb całkowitych. Rozwinięty wielomian będzie zawierał potęgi $większe$ liczba Frobeniusa dla jakiegoś wykładnika (gdy GCD = 1), np. dla ${\ Displaystyle (1 + x ^ {6) } + x ^ {7}) ^ {n}}$ zbiór to {6, 7} , który ma liczbę Frobeniusa równą 29, więc termin z ${\ displaystyle x ^ {29}}$ nigdy nie pojawi się dla żadnej wartości z $n}$ $displaystyle$ , ale pewna wartość da wyrazy o dowolnej potędze $n$ niż 29. Kiedy NWD wykładników nie wynosi 1, wówczas potęgi większe niż pewna wartość będą równe n {\ displaystyle pojawiają się tylko wtedy, gdy są wielokrotnością NWD, np. for ${\ Displaystyle (1 + x ^ {9} + x ^ {15}) ^ {n}}$ , potęgi 24 , 27, ... pojawi się dla $17$ wartości, ale nigdy wartości większych niż 24, które nie są wielokrotnościami 3 (ani mniejszych wartości, 1-8, 10-14, 16, , 19-23).

Zobacz też

Linki zewnętrzne

Jak zamówić 43 Chicken McNuggets – Numberphile