🪙 Το Πρόβλημα των Κερμάτων, ο Αριθμός του Frobenius και τα McNuggets

Φανταστείτε ότι διαθέτουμε μόνο κέρματα των 5 και 11 λεπτών. Μπορούμε να σχηματίσουμε τα 27 λεπτά:

\[ 27=5+11+11. \]

Μπορούμε επίσης να σχηματίσουμε τα 53 λεπτά:

\[ 53=4\cdot5+3\cdot11. \]

Τα 39 λεπτά όμως είναι αδύνατο να σχηματιστούν. Και εδώ εμφανίζεται μια πολύ ωραία ερώτηση:

Ποιο είναι το μεγαλύτερο ποσό που δεν μπορούμε να σχηματίσουμε χρησιμοποιώντας μόνο κέρματα των 5 και 11 λεπτών;

Η απάντηση είναι ακριβώς 39. Κάθε ακέραιο ποσό μεγαλύτερο από 39 μπορεί να γραφτεί χρησιμοποιώντας κατάλληλο αριθμό από 5άρια και 11άρια.

Αυτό δεν είναι σύμπτωση. Πρόκειται για το κλασικό πρόβλημα των κερμάτων ή πρόβλημα του Frobenius: αν έχουμε θετικούς ακεραίους και θέλουμε να σχηματίσουμε αριθμούς χρησιμοποιώντας μη αρνητικά ακέραια πολλαπλάσιά τους, ποιος είναι ο μεγαλύτερος αριθμός που δεν μπορεί να σχηματιστεί;

Όταν έχουμε μόνο δύο πρώτους μεταξύ τους θετικούς ακεραίους \(a\) και \(b\), υπάρχει μια εντυπωσιακά απλή απάντηση:

\[ g(a,b)=ab-a-b. \]

Επομένως,

\[ g(5,11)=5\cdot11-5-11=39. \]

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

Τα McNuggets μπαίνουν στα Μαθηματικά

Τα Chicken McNuggets πωλούνταν παλαιότερα, μεταξύ άλλων, σε πακέτα των 6, 9 και 20 τεμαχίων. Έτσι προκύπτει φυσικά το ερώτημα:

Ποιος είναι ο μεγαλύτερος αριθμός McNuggets που δεν μπορούμε να αγοράσουμε χρησιμοποιώντας μόνο τέτοια πακέτα;

Μαθηματικά αναζητούμε τον μεγαλύτερο αριθμό που δεν γράφεται στη μορφή

\[ 6x+9y+20z, \qquad x,y,z\in\mathbb Z_{\ge0}. \]

Η απάντηση είναι ο αριθμός

\[ \boxed{43} \]

Πράγματι, τα 43 McNuggets δεν μπορούν να σχηματιστούν. Αν δεν πάρουμε πακέτο των 20, τα πακέτα των 6 και 9 δίνουν μόνο πολλαπλάσια του 3. Αν πάρουμε ένα πακέτο των 20, απομένουν 23, που επίσης δεν σχηματίζονται από 6 και 9. Δύο πακέτα των 20 αφήνουν μόλις 3, που επίσης δεν μπορεί να προκύψει.

Από την άλλη, οι έξι διαδοχικοί αριθμοί από το 44 έως το 49 μπορούν όλοι να σχηματιστούν:

\[ \begin{aligned} 44&=4\cdot6+20,\\ 45&=5\cdot9,\\ 46&=6+2\cdot20,\\ 47&=3\cdot9+20,\\ 48&=8\cdot6,\\ 49&=9+2\cdot20. \end{aligned} \]

Και επειδή από οποιονδήποτε από αυτούς μπορούμε να προσθέτουμε πακέτα των 6, προκύπτει κάθε μεγαλύτερος ακέραιος. Έτσι,

\[ g(6,9,20)=43. \]

Ένα πρόβλημα που ξεκινά με κέρματα και κουτιά φαγητού καταλήγει λοιπόν σε ένα όμορφο ερώτημα της θεωρίας αριθμών: ποιοι ακέραιοι μπορούν να δημιουργηθούν από μη αρνητικούς ακέραιους συνδυασμούς κάποιων δεδομένων αριθμών;

📚

Έρχεται το πολλαπλό βιβλίο ΝΕΟ — βρες όλες τις επιλογές εδώΠολλαπλό βιβλίο ΝΕΟ — 437 βιβλία σε PDF

PDF & Ψηφιακά Μαθησιακά Αντικείμενα — χωρίς εγγραφή • Portify

📚 437 βιβλία🎬 22.000+ Ψηφιακά Μαθησιακά Αντικείμενα

Δες τα βιβλία →