Problema monedei

În matematică , o problemă a monedei este fiecare clasă de probleme de formă generală:

Trebuie doar anumite monede de utilizare, spun șapte- quatloo și monede de zece quatloo (The quatloo este o monedă prezentate într - un episod din Star Trek). Puteți avea câte monede din fiecare confesiune doriți; poți face modificarea exactă pentru fiecare număr de quatloo sau poți avea toate numerele de la o anumită sumă înainte ? (În exemplu, nu există nicio modalitate de a schimba opt patru-uri, dar se poate obține orice număr mai mare decât Q 53.) Dacă este posibil, care este magnitudinea sa? (Această nevoie nu este vorba doar de monede, dar aceeași întrebare poate fi pusă pentru timbre, cutii sau numărul McNugget ).

Dacă toate monedele sunt un număr par de patru, nu se pot face schimburi exacte pentru niciun număr impar de patru; acest lucru va fi adevărat chiar dacă denumirile de monede au trei sau mai multe numere ca divizor comun . Într-un limbaj mai precis, avem:

Dat fiind n numere întregi pozitive:

a_{1},a_{2},\dotsb ,a_{n}

{\ displaystyle a_ {1}, a_ {2}, \ dotsb, a_ {n}}

{\ displaystyle a_ {1}, a_ {2}, \ dotsb, a_ {n}}

, al cărui cel mai mare divizor comun

\operatorname {MCD} (a_{1},\dots ,a_{n})

{\ displaystyle \ operatorname {MCD} (a_ {1}, \ dots, a_ {n})}

{\ displaystyle \ operatorname {MCD} (a_ {1}, \ dots, a_ {n})}

este 1, găsiți cel mai mare număr N care nu poate fi exprimat ca

a_{1}x_{1}+a_{2}x_{2}+\dotsb +a_{n}x_{n},

{\ displaystyle a_ {1} x_ {1} + a_ {2} x_ {2} + \ dotsb + a_ {n} x_ {n},}

{\ displaystyle a_ {1} x_ {1} + a_ {2} x_ {2} + \ dotsb + a_ {n} x_ {n},}

pentru un număr întreg non-negativ

x_{1},x_{2},\dotsb ,x_{n}

{\ displaystyle x_ {1}, x_ {2}, \ dotsb, x_ {n}}

{\ displaystyle x_ {1}, x_ {2}, \ dotsb, x_ {n}}

.

Dacă cel mai mare divizor comun nu este egal cu 1 atunci $Nu.$ ${\ displaystyle N}$ $Nu.$ nu există, deoarece numai multiplii GCD pot fi scrise ca combinații liniare ca mai sus; dar dacă GCD este 1, atunci $Nu.$ ${\ displaystyle N}$ $Nu.$ există. Cel mai mare număr găsit este uneori numit numărul Frobenius , în timp ce ecuația diofantină

b=a_{1}x_{1}+a_{2}x_{2}+\dotsb +a_{n}x_{n}

{\ displaystyle b = a_ {1} x_ {1} + a_ {2} x_ {2} + \ dotsb + a_ {n} x_ {n}}

{\ displaystyle b = a_ {1} x_ {1} + a_ {2} x_ {2} + \ dotsb + a_ {n} x_ {n}}

se numește uneori ecuația lui Frobenius .

Soluții

Problema monedei a fost rezolvată pentru $n=1,2$ ${\ displaystyle n = 1,2}$ ${\ displaystyle n = 1,2}$ . Nu se cunoaște nicio soluție de formă închisă $n>2$ ${\ displaystyle n> 2}$ $n> 2$ .

n = 1

De sine $n=1$ ${\ displaystyle n = 1}$ $n = 1$ , atunci dacă nu $a_{1}=1$ ${\ displaystyle a_ {1} = 1}$ ${\ displaystyle a_ {1} = 1}$ , vor exista numere infinite de numere întregi pozitive m care nu pot fi exprimate ca $m=a_{1}x_{1}$ ${\ displaystyle m = a_ {1} x_ {1}}$ ${\ displaystyle m = a_ {1} x_ {1}}$ (cele care nu sunt divizibile cu $a_{1}$ ${\ displaystyle a_ {1}}$ $a_1$ ).

n = 2

De sine $n=2$ ${\ displaystyle n = 2}$ $n = 2$ , numărul Frobenius poate fi găsit prin formula $b=a_{1}a_{2}-a_{1}-a_{2}$ ${\ displaystyle b = a_ {1} a_ {2} -a_ {1} -a_ {2}}$ ${\ displaystyle b = a_ {1} a_ {2} -a_ {1} -a_ {2}}$ . Această formulă a fost descoperită de James Joseph Sylvester în 1884 .

n = 3

Algoritmii rapide sunt cunoscuți pentru trei numere, deși calculul poate fi foarte obositor atunci când se face manual.

Elemente conexe

Identitate_de_Bézout

linkuri externe

http://mathworld.wolfram.com/CoinProblem.html , la mathworld.wolfram.com .

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică