Αφαιρώντας μάρκες

[ealexiou]

Δύο παίκτες παίζουν αφαιρώντας εναλλάξ μάρκες από από ένα σωρό με μάρκες. Ο πρώτος παίκτης στην πρώτη κίνηση μπορεί να πάρει όσες μάρκες θέλει, δεν μπορεί, φυσικά, να αφαιρέσει ολόκληρο το σωρό. Μετά την πρώτη κίνηση του πρώτου παίκτη, οποιοσδήποτε παίκτης αφαιρεί τουλάχιστον μία μάρκα έως το πολύ διπλάσιες όσων πήρε ο αντίπαλος του κατά την προηγούμενη κίνηση του (π.χ αν ένας παίκτης πάρει τρεις μάρκες σε κάποια κίνηση του, αυτός που παίζει μετά μπορεί να πάρει από μία έως το πολύ έξι . Ο παίκτης που παίρνει την τελευταία μάρκα κερδίζει το παιχνίδι. Υπάρχει στρατηγική για ένα εκ των δύο να κερδίσει το παιχνίδι;

[Demetres]

Στο παιγνίδι έχουμε τους ίδιους ακριβώς κανόνες μόνο που αρχίζουμε με μάρκες και στην πρώτη του κίνηση ο πρώτος παίκτης δικαιούται να αφαιρέσει το πολύ μάρκες. Π.χ. στο πρόβλημα μας ενδιαφέρει το παιγνίδι .

Έστω το μικρότερο ώστε ο πρώτος παίκτης να κερδίζει το παιγνίδι . Είναι απλό ότι και . Μετά έχω αφού στο παιχνίδι αν αφαιρεθεί μία μάρκα τότε θα ξεκινάει ο δεύτερος παίκτης το παιγνίδι το οποίο μπορεί να κερδίσει ενώ αν αφαιρεθούν δύο μάρκες θα ξεκινάει ο δεύτερος παίκτης το παιγνίδι το οποίο πάλι κερδίσει. Μετά παίρνω αφού αν ο πρώτος παίκτης αφαιρέσει μία μάρκα τότε θα ξεκινάει ο δεύτερος παίκτης το παιγνίδι το οποίο γνωρίζουμε ήδη ότι δεν μπορεί να κερδίσει αφού . Προχωρώντας έτσι βρίσκουμε κ.τ.λ.

Με αρκετή προσοχή (ή με την βοήθεια υπολογιστή) μπορούμε να υπολογίσουμε και το . Βγαίνει . Οπότε ο πρώτος παίκτης έχει στρατηγική νίκης και στην πρώτη του κίνηση πρέπει να αφαιρέσει τρεις μάρκες.

Για να γίνει πιο ενδιαφέρον το ερώτημα, ας υπολογιστεί το . (Εδώ ο υπολογιστής δεν μπορεί να μας βοηθήσει!) Νομίζω πλέον ότι αυτό το ερώτημα είναι για διαγωνισμό Seniors.

[ealexiou]

Δημήτρη, πράγματι για τον αριθμό νικητής είναι ο πρώτος παίχτης και η αφαίρεση μαρκών από τον πρώτο παίκτη είναι μια σωστή κίνηση. Υπάρχει όμως πολύ πιο εύκολη και πολύ πιο ξεκούραστη μέθοδος-στρατηγική, έτσι που αν δοθεί ένας αριθμός σχεδόν άμεσα μπορούμε να υπολογίσουμε και να βρούμε αν νικητής θα είναι: α) O πρώτος και ποιόν αριθμό πρέπει να αφαιρέσει, ή β) νικητής θα είναι ο δεύτερος, οπότε κάνοντας την “κίνηση” του ο πρώτος, ο δεύτερος έρχεται στην θέση του πρώτου της (α) περίπτωσης και κάνει αντίστοιχα τις σωστές κινήσεις.
Έτσι στην (α) περίπτωση, που νικητής θα είναι ο πρώτος, κάνοντας ο πρώτος την μοναδικά σωστή “κίνηση” ο δεύτερος όποια “κίνηση” και να κάνει ο αριθμός μαρκών που θα μείνουν οπωσδήποτε θα είναι της περίπτωσης (α) και ο πρώτος ξανακάνει εύκολα κάποιον υπολογισμό και βρίσκει τον μοναδικά σωστό αριθμό μαρκών που πρέπει να αφαιρέσει κ.ο.κ για κάποιους κύκλους που επαναλαμβάνεται η ίδια μέθοδος υπολογισμού. Αυτά ισχύουν και για μεγαλύτερους αριθμούς από το , π.χ αν ο αριθμός μαρκών είναι ο εύκολα βρίσκουμε ποιός μπορεί να είναι ο νικητής και αν είναι ο πρώτος παίκτης ποιο αριθμό μαρκών να αφαιρέσει, γνωρίζοντας την μέθοδο-στρατηγική βέβαια.
Όπως υπολόγισες για αριθμό μαρκών: νικητής είναι ο δεύτερος παίκτης, νικητής ο δεύτερος, νικητής ο πρώτος παίκτης, νικητής ο δεύτερος, για μάρκες νικητής θα είναι ο πρώτος παίκτης... κ.λ.π....

[ealexiou]

Κάθε θετικός αριθμός, που δεν είναι όρος της ακολουθίας , μπορεί να εκφρασθεί μονοσήμαντα ως άθροισμα διαφορετικών αριθμών , χωρίς στην έκφραση αυτή να εμφανισθούν δύο διαδοχικοί αριθμοί. Ένας αριθμός Fibonacci δεν μπορεί να εκφρασθεί ως άθροισμα μη διαδοχικών αριθμών παρά μόνο ως έκφραση του εαυτού του (και του )
Αν ο αριθμός του παιχνιδιού είναι αριθμός , νικητής είναι ο δεύτερος παίχτης.
Σωστά βρήκε ο Δημήτρης ότι για τον αριθμό , για τον , και αν συνέχιζες Δημήτρη θα έβρισκες
Αν ο αριθμός του παιχνιδιού δεν είναι αριθμός , νικητής είναι ο πρώτος παίχτης, ο οποίος εκφράζει τον αριθμό ως άθροισμα διαφορετικών, μη διαδοχικών, αριθμών αρχίζοντας από τον μεγαλύτερο πλησιέστερο αριθμό , στην περίπτωση μας ο , έτσι , άρα . Δεν χρειάζεται όμως να φτάσουμε μέχρι τέλους, σταματάμε στην περίπτωση του αριθμού στο και αφαιρούμε το και αφήνουμε για τον ο παίκτη τον , καθώς και δεν μπορεί ο δεύτερος παίκτης να μας αφήσει αριθμό .
Το ίδιο και στην περίπτωση του αριθμού , ο πλησιέστερος αριθμός είναι ο και αναλύοντας έχουμε , δεν χρειάζεται να φτάσουμε μέχρι το για να το αφαιρέσουμε. Αφαιρούμε το , καθώς και ο δεύτερος αφαιρώντας έως και μας αφήνει αριθμό μη Fibonacci και η διαδικασία επαναλαμβάνεται.
Ένα παράδειγμα με μικρούς αριθμούς. Έστω ότι ο αριθμός είναι ο . Το παιχνίδι το κερδίζει ο ος παίκτης. , αφαιρεί μάρκες. Μένουν , έστω ότι ο ος αφαιρεί μάρκες, μένουν , , αφαιρούμε μία, μένουν , ο δεύτερος έστω ότι αφαιρεί μία, μένουν ,
αφαιρούμε μία, μένουν . Ο δεύτερος έστω μία, μένουν , αφαιρούμε , μένουν , ο δεύτερος αναγκαστικά μία ή δύο μπορεί να αφαιρέσει . . Αφαιρούμε αντίστοιχα δύο ή μία, μένουν για τον δεύτερο, αναγκαστικά αφαιρεί μία, μένουν . Αφαιρούμε μία και τελειώσαμε.

[Demetres]

Ευθύμη, αυτή ήταν και η μέθοδος που είχα βρει. Νομίζω όμως πως το να βρεθεί αυτό αλλά και να αποδειχθεί δεν είναι και τόσο απλό.

Παρεμπιπτόντως, καλό είναι οι seniors να γνωρίζουν ότι κάθε αριθμός γράφεται με μοναδικό τρόπο ως άθροισμα μη διαδοχικών αριθμών Fibonacci. Στην συγκεκριμένη περίπτωση η γνώση του ευκολύνει αρκετά στο να βρεθεί η στρατηγική. Το αποτέλεσμα ονομάζεται θεώρημα Zeckendorf και το έχουμε δει εδώ.

[gbdalako]

Ευθύμη, ωραίο πρόβλημα πράγματι. Υποθέτω ότι έχουμε ένα παρόμοιο χόμπυ

[gbaloglou]

Ευθύμη, ωραίο πρόβλημα πράγματι. Υποθέτω ότι έχουμε ένα παρόμοιο χόμπυ

Γιώργο ο Ευθύμης δεν είναι πια μαζί μας, απεβίωσε στις αρχές του 2022 -- σ' ευχαριστούμε όμως που μας τον θύμισες!

[gbdalako]

Ζητάω ειλικρινά συγνώμη, λοιπόν - δεν ήξερα.
Αιωνία του η μνήμη.

[gbaloglou]

Ζητάω ειλικρινά συγνώμη, λοιπόν - δεν ήξερα.
Αιωνεία του η μνήμη.

Καινούργιος είσαι, πως να το ήξερες;! Βλέπε κάποια σχόλια εδώ.