Euler 2014-3

[Demetres]

Εξωγήινοι έχουν απαγάγει επιστήμονες από την γη για να ελέγξουν την εξυπνάδα τους. Έχουν έτοιμες ρόμπες αριθμημένες στο πίσω μέρος τους από το ως το . Την μέρα του τεστ μια από τις ρόμπες θα αφαιρεθεί τυχαία και οι υπόλοιπες θα φορεθούν τυχαία από μία σε κάθε επιστήμονα. Οι επιστήμονες θα σταθούν σε μία γραμμή, πάλι τυχαία, έτσι που ο κάθε επιστήμονας θα βλέπει τον αριθμό της ρόμπας του μπροστινού του αλλά όχι τον δικό του ή αυτών που βρίσκονται πίσω του. Με όποια σειρά θέλουν οι επιστήμονες μπορούν να ξεκινήσουν να ανακοινώνουν από ένα αριθμό προσπαθώντας να μαντέψουν τον αριθμό της ρόμπας τους. Κάθε αριθμός ρόμπας μπορεί να ανακοινωθεί μόνο από ένα επιστήμονα. Όταν ανακοινωθεί οι επόμενοι επιστήμονες απαγορεύεται να μαντέψουν αυτόν τον αριθμό. Κάθε επιστήμονας που μαντεύει λανθασμένα σκοτώνεται αμέσως και αθόρυβα ενώ όποιος μαντεύει σωστά ελευθερώνεται. Οι επιστήμονες έχουν μια μέρα για να αποφασίσουν την στρατηγική τους. Σκοπός τους είναι να μειώσουν τον προσδοκόμενο αριθμό θανάτων. Τι στρατηγική πρέπει να ακολουθήσουν;

[ealexiou]

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

Ένα παράδειγμα με ανθρώπους και το σύνολο των αριθμών και έστω ότι η γραμμή από τον πρώτο προς τον είναι
, ανακοινώνει
, ανακοινώνει
, ανακοινώνει
, ο άτυχος δεν μπορεί να πει το (το είπε ο ) και ανακοινώνει (τον αριθμό του ) και ο αντιλαμβάνεται ότι ο είχε το
, ανακοινώνει
Δεν μπορεί να πει το , οπότε λέει ή

Περίπτωση εύνοιας της τύχης και για τους , έστω ότι οι αριθμοί είναι
, ανακοινώνει , οι υπόλοιποι ως ανωτέρω και σώζονται όλοι.

Περίπτωση με άτυχους τον πρώτο και τον τελευταίο ,

[ealexiou]

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

Για επιστήμονες και έναν εικονικό για να έχουμε όλη την μετάθεση των αριθμών
Έστω ότι η γραμμή-μετάθεση από τον πρώτο προς τον τελευταίο είναι
βλέπει οπότε έχει ή ή και άρα ή (περιττή) ή (άρτια), οπότε λέει και χάνει την ζωή του, άτυχος...
βλέπει , άκουσε οπότε έχει ή , άρα ή (άρτια) ή (περιττή) επιλέγει την άρτια, άρα λέει και σώζεται.
βλέπει , άκουσε άρα έχει ή άρα ή (άρτια) ή (περιττή), επιλέγει την άρτια λέει και σώζεται.
άκουσε , άρα έχει ή ή , ήτοι ή (άρτια) ή (, περιττή), επιλέγει την άρτια και λέει και σώζεται.

[Demetres]

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

Ουσιαστικά η ίδια άσκηση εμφανίστηκε και στο τουρνουά των πόλεων την άνοιξη του 2013. Ήταν το 7ο πρόβλημα από το Senior A Level. Υπάρχει και ως άσκηση 95 στο φυλλάδιο που ανέβασα εδώ. Όπως το διατύπωσα εκεί, υπάρχει ένα λαθάκι στην εκφώνηση που επιτρέπει μια πολύ εύκολη λύση. Θα το διορθώσω σύντομα. Προς το παρόν προσπαθήστε να βρείτε τι παρέλειψα από την εκφώνηση και γιατί το κάνει πιο εύκολο.

[ealexiou]

Δημήτρη καλησπέρα
Και ο ίδιος αναφέρθηκα στην κατά πενήντα στα εκατό (δεν μπορώ να το γράψω αριθμητικά στο LaTex, βγαίνει σκέτο το και έτσι έγραψα .
" Έτσι σώζονται και οι , και ο με πιθανότητα σώζεται, αν συμπέσει ο αριθμός που θα επιλέξει με τον αριθμό της ρόμπας του, αν όχι (έχει τον άλλον αριθμό) χάνει την ζωή του", εκτός αν εννοείς ότι δεν έκανα την πρόσθεση , οπότε τυπικά σωστή η παρατήρηση σου.
Ευθύμης

[Demetres]

Συγνώμη, δεν το πρόσεξα.

Παρεμπιπτόντως στο latex γράφουμε \% αντί μόνο % για να εμφανιστεί το ποσοστό.

[ealexiou]

Σε αυτό εδώ υπάρχει ο περιορισμός “Με όποια σειρά θέλουν οι επιστήμονες μπορούν να ξεκινήσουν να ανακοινώνουν από ένα αριθμό προσπαθώντας να μαντέψουν τον αριθμό της ρόμπας τους.

Στο 95 λέει “Ξεκινώντας από τον τελευταίο σοφό θα προσπαθήσουν όλοι με την σειρά να μαντέψουν τον αριθμό του καπέλου τους.” Δεν υπάρχει περιορισμός στο πόσους αριθμούς μπορούν να πουν, οπότε ο τελευταίος θα πει τους δύο που δεν βλέπει και οι υπόλοιποι βρίσκουν ευκολότατα τον αριθμό τους.

[Demetres]

Χα, δεν το σκέφτηκα ότι μπορεί να παρερμηνευτεί και αυτό! Η δική μου παρατήρηση είναι ότι ο τελευταίος μπορεί να μαντέψει το άθροισμα των αριθμών που βλέπει (δεν υπάρχει περιορισμός ότι πρέπει ο αριθμός να είναι από το 1 ως το 1001) οπότε οι υπόλοιποι μαντεύουν εύκολα τον αριθμό τους.

Ούτε στο πρόβλημα του Euler έβαλα αυτόν τον περιορισμό αλλά δεν χρειάζεται! Αν κάνουν την πιο πάνω κλεψιά ο προσδοκόμενος αριθμός που σώζεται είναι 99 και όχι 99.5!