Το Πρόβλημα των Νομισμάτων και ο Αριθμός του Frobenius – Από τα 5 και 8 ευρώ στη Θεωρία Αριθμών

Αν έχετε δύο αριθμούς — για παράδειγμα το 5 και το 8 — και σας ζητήσουν να γράψετε το 120 ως άθροισμα πολλαπλασίων αυτών των δύο:

$$5x+8y=120,x,y\ge 0$$

πόσες λύσεις υπάρχουν;

Και ποιο είναι το μεγαλύτερο ποσό που δεν μπορεί να γραφτεί με τέτοιον τρόπο;

---

Από το Παζάρι στα Μαθηματικά

Φανταστείτε ότι έχετε νομίσματα των 5 και 8 ευρώ.
Μπορείτε να σχηματίσετε ποσά όπως 5, 8, 10, 13, 15, 16, … και συνεχίζετε.

Όμως υπάρχουν κάποια ποσά που δεν μπορούν να σχηματιστούν — π.χ. 1, 2, 3, 4, 6, 7, 9, 11, 12 κ.λπ.

Κάποια στιγμή, όμως, τα “κενά” εξαφανίζονται. Από ένα σημείο και μετά, όλοι οι αριθμοί μπορούν να παρασταθούν με τέτοιον συνδυασμό.
Το ερώτημα είναι: ποιος είναι ο τελευταίος αριθμός που δεν μπορεί να γραφτεί έτσι;

---

Το Θεώρημα του Frobenius

Για δύο θετικούς αμοιβαία πρώτους αριθμούς $a, b$ (δηλαδή $\gcd(a,b)=1$,
ο μεγαλύτερος αριθμός που δεν μπορεί να γραφτεί ως $a x + b y$ με $x, y \ge 0$ είναι:

$$N=ab-a-b$$

Αυτός ο αριθμός λέγεται αριθμός Frobenius.

Τον τύπο απέδειξε ο Γερμανός μαθηματικός Ferdinand Frobenius τον 19ο αιώνα, επεκτείνοντας ιδέες που ξεκινούν από τον Sylvester και τον Diophantus.

---

Παράδειγμα: 5 και 8

Αν $a = 5$ και $b = 8$, τότε:

$$N=5\times 8-5-8=27$$

👉 Άρα το 27 είναι το μεγαλύτερο ποσό που δεν μπορεί να σχηματιστεί με νομίσματα των 5 και 8 ευρώ.

Από το 28 και πάνω, κάθε αριθμός μπορεί να γραφτεί ως $5x + 8y$ με $x, y \ge 0$.

---

Πόσες λύσεις υπάρχουν για κάθε αριθμό;

Για $\gcd(a,b)=1$, η εξίσωση $a x + b y = c$ έχει πλήθος λύσεων:

$$N(c)=\lfloor \frac{\lfloor c\mathrm{/}a\rfloor -x_0}{b}\rfloor +1$$

όπου $x_0$ είναι η μικρότερη μη αρνητική λύση της $a x \equiv c \pmod b$.

Στο παράδειγμά μας, $5x + 8y = 120$:

$$(x,y)=(24,0),(16,5),(8,10),(0,15)$$

δηλαδή 4 λύσεις.

---

Η Περιοδικότητα των Λύσεων

Κάθε φορά που αυξάνουμε το $c$ κατά $a b$, έχουμε:

$$N(c + ab) = N(c) + 1$$

και το μοτίβο των λύσεων επαναλαμβάνεται περιοδικά, δημιουργώντας ένα όμορφο αριθμητικό πλέγμα.

---

Πέρα από την Εξίσωση

Μια απλή εξίσωση όπως $a x + b y = c$ περιέχει μέσα της:

• τη λογική της modular arithmetic,

• την έννοια της πληρότητας (ότι μετά από ένα σημείο δεν υπάρχουν “τρύπες”),

• και τη συνδυαστική αρμονία των λύσεων.

Από τα “νομίσματα” του Frobenius, μέχρι τα αλγοριθμικά προβλήματα και τη βιομηχανική βελτιστοποίηση, η ίδια ιδέα επιστρέφει: η διακριτή δομή των αριθμών εξηγεί τη συνέχεια του κόσμου.

---

📘 Ιστορική Νότα

Το “Coin Problem” γεννήθηκε τον 19ο αιώνα ως ψυχαγωγικό μαθηματικό ερώτημα: πόσα ποσά μπορούν να σχηματιστούν με νομίσματα συγκεκριμένων αξιών;

Από τότε εξελίχθηκε σε ολόκληρο κεφάλαιο της θεωρίας αριθμών, με εφαρμογές στην αλγοριθμική, στα οικονομικά μοντέλα και στην υπολογιστική θεωρία.