Euler 2014-3

Συντονιστής: Demetres

Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 8549
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

Euler 2014-3

#1

Μη αναγνωσμένη δημοσίευση από Demetres » Πέμ Ιούλ 17, 2014 12:33 pm

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



Λέξεις Κλειδιά:
ealexiou
Δημοσιεύσεις: 1658
Εγγραφή: Παρ Νοέμ 15, 2013 10:06 pm
Τοποθεσία: ΒΟΛΟΣ

Re: Euler 2014-3

#2

Μη αναγνωσμένη δημοσίευση από ealexiou » Κυρ Αύγ 24, 2014 11:14 pm

Βρήκαν και συμφώνησαν την παρακάτω περιγραφόμενη στρατηγική (υπάρχει και καλύτερη, αλλά θέλω να το μελετήσω καλύτερα)
Ο 100os θα ανακοινώσει τον αριθμό που αντιστοιχεί στο ισοδύναμο (mod) του αθροίσματος των αριθμών που έχουν οι 99 προηγούμενοι του έστω a mod101, 0 \leq a \leq 100, (στην περίπτωση που a=0 ανακοινώνει φυσικά 101) και χάνει την ζωή του εκτός της περίπτωσης που το a θα συμπέσει με τον αριθμό της μπλούζας του.
Ο 99os , έστω ότι έχει τον αριθμό x, αθροίζει τους αριθμούς που βλέπει μπροστά του, βγάζει το ισοδύναμο του αθροίσματος αυτού, έστω b οπότε επειδή x+b=a \Rightarrow x \equiv (a-b) mod101 και ανακοινώνει τον αριθμό του και στην περίπτωση που (a-b)<0, τον θετικό αριθμό που είναι ισοδύναμος με (a-b) mod101.
Ο 98os αθροίζει τους αριθμούς που είναι μπροστά του (και οι επόμενοι από πίσω προς τα εμπρός το ίδιο κάνουν) τον αριθμό που ανακοινώθηκε πίσω του (τους αριθμούς που ανακοινώθηκαν πίσω τους για τους επόμενους) και λύνει (λύνουν) την εξίσωση άθροισμα αριθμών +x=amod101 και μέχρι τον άτυχο με τον αριθμό a, που ήδη ανακοινώθηκε, που όταν έρθει η σειρά του, δεν μπορεί να ανακοινώσει τον αριθμό του και θα ανακοινώσει τον αριθμό του 1o \upsilon (και χάνει την ζωή του, δύο οι άτυχοι ) και έτσι δίνει την πληροφορία στους μπροστινούς του για τον αριθμό του, οι επόμενοι με τον ίδιο τρόπο βρίσκουν τους αριθμούς τους και ο 1os θα πει ένα από τα δύο πιθανά που μπορεί να είχε ο 100os και χάνει την ζωή του.
Έτσι η διαδικασία ολοκληρώνεται με τουλάχιστον 97 να σώζονται, (η περίπτωση της εύνοιας της τύχης ισχύει, το a να είναι ο αριθμός που έχει η ρόμπα του ο 100os επιστήμονας και έτσι σώζονται όλοι! Και μία δεύτερη περίπτωση τύχης είναι το a να είναι ο αριθμός του 1o \upsilon, οπότε σώζονται 98 με άτυχους τον 1o και τον 100o).

Ένα παράδειγμα με 6 ανθρώπους και το σύνολο των αριθμών 1,2,3,4,5,6,7 και έστω ότι η γραμμή από τον πρώτο προς τον 6ο είναι 5,2,1,4,3,7
6os: (5+2+1+4+3) mod7   \equiv 1, ανακοινώνει 1
5os: (5+2+1+4) mod7  \equiv 5,  x+5=1 \Rightarrow  x  \equiv -4mod7  \equiv 3mod7, ανακοινώνει 3
4os: (5+2+1) mod7  \equiv 1, x+1+3=1 \Rightarrow  x  \equiv -3 mod7  \equiv 4mod7, ανακοινώνει 4
3os: (5+2) mod7   \equiv 0mod7, x+0+4+3=1 \Rightarrow x \equiv -6mod7 \equiv 1mod7, ο άτυχος δεν μπορεί να πει το 1 (το είπε ο 6os) και ανακοινώνει 5 (τον αριθμό του 1o\upsilon) και ο 2os αντιλαμβάνεται ότι ο 3os είχε το 1
2os: 5=5mod7, x+5+1+4+3=1 \Rightarrow  x  \equiv -12mod7 \equiv 2 mod7, ανακοινώνει 2
1os: Δεν μπορεί να πει το 5, οπότε λέει 6 ή 7

Περίπτωση εύνοιας της τύχης και για τους 6, έστω ότι οι αριθμοί είναι 5,2,1,7,3,4
6os (5+2+1+7+3)  \equiv 4 mod7, ανακοινώνει 4, οι υπόλοιποι ως ανωτέρω και σώζονται όλοι.

Περίπτωση με άτυχους τον πρώτο και τον τελευταίο 7,2,5,3,4,1, (7+2+5+3+4) mod7 \equiv 7


ealexiou
Δημοσιεύσεις: 1658
Εγγραφή: Παρ Νοέμ 15, 2013 10:06 pm
Τοποθεσία: ΒΟΛΟΣ

Re: Euler 2014-3

#3

Μη αναγνωσμένη δημοσίευση από ealexiou » Δευ Αύγ 25, 2014 10:35 pm

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

Για 4 επιστήμονες και έναν εικονικό για να έχουμε όλη την μετάθεση των 5 αριθμών (12345)
Έστω ότι η γραμμή-μετάθεση από τον πρώτο προς τον τελευταίο είναι 2134
4os: βλέπει 213 οπότε έχει ή 4 ή 5 και άρα ή 21345 (περιττή) ή 21354 (άρτια), οπότε λέει 5 και χάνει την ζωή του, άτυχος...
3os: βλέπει 21, άκουσε 5 οπότε έχει 3 ή 4, άρα ή 21354 (άρτια) ή 21453 (περιττή) επιλέγει την άρτια, άρα λέει 3 και σώζεται.
2os: βλέπει 2, άκουσε 35 άρα έχει 1 ή 4 άρα ή 21354 (άρτια) ή 24351 (περιττή), επιλέγει την άρτια λέει 1 και σώζεται.
1os: άκουσε 135, άρα έχει ή 2 ή 4, ήτοι ή 21354 (άρτια) ή 41352 (41325,21345,12345, περιττή), επιλέγει την άρτια και λέει 2 και σώζεται.


Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 8549
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

Re: Euler 2014-3

#4

Μη αναγνωσμένη δημοσίευση από Demetres » Τρί Αύγ 26, 2014 9:46 am

:coolspeak:

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

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


ealexiou
Δημοσιεύσεις: 1658
Εγγραφή: Παρ Νοέμ 15, 2013 10:06 pm
Τοποθεσία: ΒΟΛΟΣ

Re: Euler 2014-3

#5

Μη αναγνωσμένη δημοσίευση από ealexiou » Τρί Αύγ 26, 2014 1:50 pm

Δημήτρη καλησπέρα
Και ο ίδιος αναφέρθηκα στην κατά πενήντα στα εκατό (δεν μπορώ να το γράψω αριθμητικά στο LaTex, βγαίνει σκέτο το 50 και έτσι έγραψα 0,50 ( \dfrac{1}{2}).
" Έτσι σώζονται και οι 99, και ο 100os με πιθανότητα 0,50 σώζεται, αν συμπέσει ο αριθμός που θα επιλέξει με τον αριθμό της ρόμπας του, αν όχι (έχει τον άλλον αριθμό) χάνει την ζωή του", εκτός αν εννοείς ότι δεν έκανα την πρόσθεση 99+0.5=99.5 , οπότε τυπικά σωστή η παρατήρηση σου.
Ευθύμης


Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 8549
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

Re: Euler 2014-3

#6

Μη αναγνωσμένη δημοσίευση από Demetres » Τρί Αύγ 26, 2014 1:57 pm

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

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


ealexiou
Δημοσιεύσεις: 1658
Εγγραφή: Παρ Νοέμ 15, 2013 10:06 pm
Τοποθεσία: ΒΟΛΟΣ

Re: Euler 2014-3

#7

Μη αναγνωσμένη δημοσίευση από ealexiou » Τετ Αύγ 27, 2014 8:31 am

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

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


Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 8549
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

Re: Euler 2014-3

#8

Μη αναγνωσμένη δημοσίευση από Demetres » Τετ Αύγ 27, 2014 10:02 am

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

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


Απάντηση

Επιστροφή σε “Διαγωνισμοί για φοιτητές”

Μέλη σε σύνδεση

Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 2 επισκέπτες