1. Έχετε ένα φύλλο χαρτί και μπορείτε να το σχίσετε σε 8 ή 12 κομμάτια. Κάθε νέο κομμάτι μπορείτε να το σχίσετε επίσης σε 8 ή 12 κομμάτια κ.ο.κ. Ποιος είναι ο μέγιστος συνολικός αριθμός κομματιών, στον οποίο είναι αδύνατο να καταλήξετε;
2. Στο τραπέζι υπάρχουν 111 κομμάτια πηλού ίσης μάζας. Σε μία κίνηση, μπορείτε με όσα θέλετε από τα υπάρχοντα κομμάτια να φτιάξετε μία ή περισσότερες ομάδες ίσου αριθμού κομματιών ανά ομάδα (όχι απαραίτητα ίσης μάζας το κάθε κομμάτι) και να ενώσετε τα κομμάτια κάθε ομάδας σε ένα ενιαίο κομμάτι. Πόσες τουλάχιστον κινήσεις θα χρειαστείτε για να φτιάξετε 11 κομμάτια διαφορετικής μάζας το καθένα;
1. Ο μέγιστος συνολικός αριθμός που δεν μπορούμε να καταλήξουμε είναι 60.
Για κάθε κομμάτι που σχίζεται σε 8 νέα κομμάτια, αυξάνεται ο συνολικός αριθμός των κομματιών κατά 7, ενώ για κάθε κομμάτι που σκίζεται στα 12, αυξάνεται ο συνολικός αριθμός των κομματιών κατά 11.
Επομένως, ο συνολικός αριθμός των κομματιών ανά πάσα στιγμή περιγράφεται από τη παράσταση (1+11*κ+7*λ), όπου κ και λ είναι μη αρνητικοί ακέραιοι, που εκφράζουν πόσα σχισίματα έχουν γίνει σε 12 και 8 κομμάτια αντίστοιχα.
Στη συνέχεια κάνουμε τους ακόλουθους μετασχηματισμούς:
Α=11κ+7λ= 7(κ+λ)+4κ, και θέτοντας κ+λ=α,
Α=7α+4κ = 4(α+κ)+3α, και θέτοντας α+κ=β,
Α=4β+3α =3(α+β)+β, και θέτοντας α+β=γ,
Α=3γ+β=(β+γ)+2γ, και θέτοντας β+γ=δ,
Α=2γ+δ, και θέτοντας γ+δ=ε,
Α=ε+γ (1)
Από τους ανωτέρω μετασχηματισμούς, προκύπτει ότι:
γ=3κ+2λ
ε=8κ+5λ
και επιλύοντας ως προς κ και λ,
κ=2ε-5γ
λ=8γ-3ε
Επειδή τα κ και λ, είναι μη αρνητικοί ακέραιοι, δηλαδή κ>=0, λ>0, συνεπάγεται ότι
2ε>=5γ
8γ>=3ε,
Και τελικά
16γ>=(6ε)>=15γ
Προσθέτοντας 6γ σε κάθε μέλος της ανωτέρω σχέσης, και δεδομένου ότι ε+γ=Α, προκύπτει ότι
22γ>=6Α>=21γ, η οποία ισοδυναμεί με:
22Α/77>γ>21Α/77 (2)
Από τον συνδυασμό των (1) και (2), συμπεραίνουμε ότι για να μπορεί ένας ακέραιος αριθμός να εκφραστεί ως δυνατός αριθμός κομματιών Α μέσω αυτης της διαδικασίας (για την ακρίβεια Α+1), θα πρέπει να υπάρχει ένας θετικός ακέραιος γ που να ευρίσκεται στο εύρος τιμών της ανίσωσης (2) ανωτέρω. Με διαφορετική διατύπωση, το ζητούμενο είναι αδύνατον, εάν οι αριθμοί 22Α/77 και 21Α/77, έχουν το ίδιο ακέραιο μέρος.
Είναι προφανές ότι για κάθε αριθμό >=77 υπάρχει ακέραιος γ που ικανοποιεί την ανωτέρω σχέση. Όμως και αρκετοί αριθμοί=60. Για να φθάσουμε σε ίδια ακέραια μέρη, θα πρέπει να φθάσουμε στον αριθμο Α=59.
Επομένως ο μέγιστος αριθμός στον οποίο είναι αδύνατο να καταλήξουμε με αυτή τη διαδικασία είναι ο Α+1=60
Η επαλήθευση ότι οποιοσδήποτε αριθμός>60, μπορεί να εκφραστεί μέσω της διαδικασίας είναι η ακόλουθη:
Εστω ακέραιος αριθμός Χ>60. Θέτουμε τον αριθμό Α=Χ-1 στην ανίσωση (2) ανωτέρω και βρίσκουμε τον ακέραιο γ που την ικανοποιεί (για μεγάλα Α, ενδεχομένως οι λύσεις είναι περισσότερες από μία).
Από τη σχέση (1), υπολογίζουμε το ε=Α-γ
Από τις σχέσεις κ=2ε-5γ και λ=8γ-3ε, υπολογίζουμε τα κ και λ, που μας δίνουν τους αριθμούς σχισιμάτων σε 12 και 8 κομμάτια αντίστοιχα.
Για παράδειγμα, έστω Χ=80
Α=80-1=79
Από την (2), 22,6>γ>21,5, άρα γ=22
Από την (1), ε=79-22=57
κ=2ε-5γ=4 και λ=8γ-3ε=5
Πράγματι, 1+4*11+5*7=80, δηλαδή με 4 σχισίματα σε 12 κομμάτια και 5 σχισίματα σε 8 κομμάτια, επιτυγχάνεται συνολικός αριθμός κομματιών 80
Πρόβλημα1
Αν καταφέρουμε να έχουμε μια 7αδα αριθμών που για αυτά να έχουμε τα αντίστοιχα κομμάτια, από εκεί και έπειτα μπορούμε να εξασφαλίζουμε κομμάτια για όλους τους αριθμούς που ακολουθούν αυτή την 7αδα. Παράδειγμα:
Εστω ότι έχουμε εξασφαλίζει τους χ,χ+1,χ+2…χ+6. Μπορούμε να πάρουμε τα χ-1 κομμάτια (από τα χ) και το τελευταίο να το σκίσουμε σε 8 τότε θα έχουμε χ-1+8=χ+7 κομμάτια. Το χ+8 εξασφαλίζεται αν πάρουμε τα χ κομμάτια (από τα χ+1) και το τελευταίο το σκίσουμε σε 8 τότε θα έχουμε χ+8. Το χ+9 εξασφαλίζεται αν πάρουμε τα χ+1 κομμάτια (από τα χ+2) και το τελευταίο το σκίσουμε σε 8 τότε θα έχουμε χ+1+8=χ+9. Το χ+10 εξασφαλίζεται αν πάρουμε τα χ+2 κομμάτια (από τα χ+3) και το τελευταίο το σκίσουμε σε 8 τότε θα έχουμε χ+2+8=χ+10 κοκ
Πότε συμβαίνει αυτό; Αυτό γίνεται από το 61 και έπειτα όπου συναντούμε την πρώτη συμπληρωμένη 7αδα αριθμών-κομματιών (61,62…,67)
Πιο συγκεκριμένα μπορούμε να πετύχουμε
Όλα τα κομμάτια με 1mod7 από 8 και έπειτα
Όλα τα κομμάτια με 2mod7 από 23 και έπειτα
Όλα τα κομμάτια με 3mod7 από 45 και έπειτα
Όλα τα κομμάτια με 5mod7 από 19 και έπειτα
Όλα τα κομμάτια με 6mod7 από 34 και έπειτα
Όλα τα κομμάτια με 0mod7 από 56 και έπειτα
Από τα παραπάνω καταλαβαίνουμε ότι μας λείπει το 4mod7 που για πάνω από το 60 ο πρώτος αριθμός είναι ο 67, αυτόν το καλύπτουμε αν πάρουμε το 56 κρατήσουμε τα 55 κομμάτια και το τελευταίο το σκίσουμε σε 12 = 55+12=67.
Πρόβλημα 1
Εκ παραδρομής δεν αναφέρθηκε ο μέγιστος δυνατός αριθμός που ΔΕΝ μπορεί να φτιαχτεί !!
Αυτός είναι ο 60 που είναι 4mod7
Πρόβλημα 2
Προς χάριν ευκολίας θεωρούμε την αρχική μάζα των 111 κομματιών ίση με 1.
Έχουμε μπροστά μας 111 (1)
Παίρνουμε 60 (1) και φτιάχνουμε 30 κομμάτια των 2 και μας έχουν μείνει 51 (1). Έχουμε κάνει μια κίνηση.
Η δεύτερη κίνηση συνίσταται στη συγκρότηση ομάδων με 3 μέλη. Συνολικά φτιάχνονται 13 ομάδες ως εξής:
6 ομάδες των (2,2,2) , 4 ομάδες των (2,2,1) , 2 ομάδες των (1,1,1) και 1 ομάδα των (1,1,2).
Έχουμε χρησιμοποιήσει 27 (2) και μας έχουν μείνει 3 (2) και επιπλέον έχουμε χρησιμοποιήσει 12 (1) και μας έχουν μείνει 39 (1).
Πλέον μετά το πέρας της δεύτερης κίνησης είναι γνωστές οι μάζες των 1, 2, 3 =>(1,1,1), 4=>(1,1,2), 5=>(2,2,1) , 6=>(2,2,2)
Αφού αφαιρέσουμε τα παραπάνω κομμάτια γνωστής πλέον μάζας έχουμε μπροστά μας
5 κομμάτια (2,2,2) , 3 κομμάτια (2,2,1) , 1 κομμάτι (1,1,1)
Με τα παραπάνω κομμάτια και με 1 (1) και 1 (2) που ήδη μας περισσεύουν, μπορούμε να φτιάξουμε μάζες 7,8,9,10,11 με μια μόνο κίνηση.
Η τρίτη κίνηση συνίσταται στη συγκρότηση ομάδων με 2 μέλη.
(2,2,2) – (1) =7
(2,2,2) – (2) =8
(2,2,2) – (1,1,1) =9
(2,2,1) – (2,2,1)=10
(2,2,2) – (2,2,1)=11
Γίνεται με 2 κινήσεις ; Λογικά όχι, μετά το τέλος της πρώτης κίνησης εκτός από το κομμάτι μάζας 1 θα έχουμε κομμάτια μιας μόνο γνωστής μάζας, έστω της χ.
Πλέον μπροστά μας θα έχουμε 1,1,1,1….χ,χ,χ,χ,χ. Στο τέλος της δεύτερης κίνησης θα έχουμε το πολύ τρεις περιπτώσεις κομματιών νέας μάζας. Κομμάτια που θα αποτελούνται μόνο από χ, κομμάτια μόνο από 1 και κομμάτια από χ και 1. Συνολικά θα έχουμε 5 γνωστές μάζες
1. Η αρχική μας εξίσωση είναι η 1+7χ+11ψ=Σ και θέτοντας Ν=Σ-1 έχουμε 7χ+11ψ=Ν
Θέτω υ το υπόλοιπο της διαίρεσης του Ν με το 7, δηλαδή υ= Νmod7.
(Ν – 0*11)mod7 = Nmod7 – 0mod7 = υ
(Ν – 1*11)mod7 = Nmod7 – 11mod7 = υ-4
(Ν – 2*11)mod7 = Nmod7 – 22mod7 = υ-1
(Ν – 3*11)mod7 = Nmod7 – 33mod7 = υ-5
(Ν – 4*11)mod7 = Nmod7 – 44mod7 = υ-2
(Ν – 5*11)mod7 = Nmod7 – 55mod7 = υ-6
(Ν – 6*11)mod7 = Nmod7 – 66mod7 = υ-3
Το υ μπορεί να πάρει τιμές από 0 έως 6, άρα σε μία από τις παραπάνω περιπτώσεις μηδενίζουμε το υπόλοιπο της διαίρεσης του αρχικού μας αριθμού με το 7. Άρα κόβοντας 1 κομμάτι στα 12 από 0 έως 6 φορές και στη συνέχεια κόβοντας τον κατάλληλο αριθμό κομματιών στα 8 παίρνουμε τον αριθμό Ν. Άρα για Ν >= 66 το ζητούμενο είναι πάντοτε εφικτό. Επίσης έχουμε τα εξής:
7*3+11*4=65
7*6+11*2=64
7*9+11*0=63
7*1+11*5=62
7*4+11*3=61
7*7+11*1=60
Δεν υπάρχει όμως συνδυασμός που να δίνει Ν=59, άρα ο μέγιστος αριθμός που δεν γίνεται να πετύχουμε είναι ο Σ= 59+1= 60.
1. Εξαιρετικές οι λύσεις από Στράτο, Κωστή και Πάνο, μπράβο παίδες!
Αναφέρω μόνο, για την ιστορία, ότι το πρόβλημα παραπέμπει στην Chicken mcNugget formula (https://artofproblemsolving.com/wiki/index.php/Chicken_McNugget_Theorem), που μας δίνει απευθείας το ζητούμενο, αφού οι 7 και 11 είναι αμοιβαία πρώτοι, άρα ο μεγαλύτερος ακέραιος που είναι αδύνατο να εκφραστεί ως 7α+11β είναι ο 7*11-7-11=59. Συνεπώς ο μεγαλύτερος ανέφικτος αριθμός κομματιών, που είναι της μορφής 1+7α+11β, είναι ο 1+59=60.
2. Πάρα πολύ ευρηματική η προσπάθεια του Κωστή, μπράβο του, αλλά είναι δυστυχώς μόλις παρά τρίχα η βέλτιστη?. Δεν έχει νόημα όμως να δώσω τη βέλτιστη ο ίδιος, αφήνω μια δύο μέρες ακόμα, μήπως τη σκεφτεί ο Κωστής ή άλλος φίλος..
Ειλικρινά είναι από τους πλέον έξυπνους γρίφους που έχω συναντήσει !! 😉
1η κίνηση => Συγκροτούμε 37 ομάδες μάζας 2 (1,1) και έχουμε και 37 (1) “ελεύθερους”, 37*2+37=111.
2η κίνηση => Έχοντας ήδη γνωστές μάζες την (1) και (2), έχουμε μπροστά μας 36 (2) και 36 (1). Συγκροτούμε 9 ομάδες των 8 με τις ακόλουθες διατάξεις
(2,2,2,2,2,2,2,2)=16
(2,2,2,2,2,2,2,1)=15
(2,2,2,2,2,2,1,1)=14
(2,2,2,2,2,1,1,1)=13
(2,2,2,2,1,1,1,1)=12
(2,2,2,1,1,1,1,1)=11
(2,2,1,1,1,1,1,1)=10
(2,1,1,1,1,1,1,1)=9
(1,1,1,1,1,1,1,1)=8
Πλέον έχουμε 11 γνωστές μάζες !!
Κωστή, σε προσκυνώ, είσαι βελτιστομεγιστοτιτανοτεράστιος, εύγε!