Έχουμε 2020 ανθρώπους σε ένα κύκλο όπου κάθε δεύτερο πρόσωπο πεθαίνει μέχρι να μείνει ένας.
Δηλαδή, ο πρώτος σκοτώνει τον δεύτερο, ο τρίτος τον τέταρτο ,ο πέμπτος τον έκτο κ.ο.κ μέχρι να μείνει ένας.
Ποιος θα μείνει;
Προτάθηκε από Αθανάσιο Δρούγα
Έχουμε 2020 ανθρώπους σε ένα κύκλο όπου κάθε δεύτερο πρόσωπο πεθαίνει μέχρι να μείνει ένας.
Δηλαδή, ο πρώτος σκοτώνει τον δεύτερο, ο τρίτος τον τέταρτο ,ο πέμπτος τον έκτο κ.ο.κ μέχρι να μείνει ένας.
Ποιος θα μείνει;
Προτάθηκε από Αθανάσιο Δρούγα
Υποθέτουμε ότι οι σκοτωμοί γίνονται με ένα μαχαίρι που κάνει κύκλους, δηλαδή αρχικά το έχει ο 1 και σκοτώνει με αυτό τον 2, το παίρνει μετά ο 3 και σκοτώνει τον 4 κ.ο.κ. Αν ο συνολικός αρχικός αριθμός ανθρώπων ήταν δύναμη του 2, τότε με τη συμπλήρωση κάθε φονικού κύκλου, το μαχαίρι θα το έπαιρνε πάντα ο 1, για να σκοτώσει τον εκάστοτε επόμενό του ζωντανό, οπότε ο 1 θα ήταν και ο τελευταίος ζωντανός. Όταν ο συνολικός αρχικός αριθμός ανθρώπων δεν είναι δύναμη του 2, τελευταίος ζωντανός θα είναι εκείνος που θα κρατάει το μαχαίρι, όταν έχουν σκοτωθεί τόσοι ώστε ο αριθμός των απομενόντων ζωντανών να γίνει δύναμη του 2. Η αμέσως μικρότερη του 2020 δύναμη του 2 είναι ο αριθμός 2^10=1024 και όταν θα έχουν μείνει 1024 ζωντανοί, τότε θα έχουν σκοτωθεί 2020-1024= 996 άνθρωποι. Δεδομένου ότι πρώτοι σκοτώνονται οι 1010 ζυγοί, ο τελευταίος που θα έχει σκοτωθεί όταν συμπληρωθούν 996 νεκροί θα είναι ο 2*996= 1992. Ο αμέσως επόμενος που θα πάρει το μαχαίρι θα είναι ο 1993, άρα αυτός θα είναι και ο τελευταίος ζωντανός.
o 1993ος
Νικητής είναι εκείνος που μετά από κάποιο γύρο το πλήθος των επιζώντων είναι δύναμη του 2 και είτε είναι ο μικρότερος και έχουν “παίξει” όλοι στον προηγούμενο γύρο, είτε είναι ο μεγαλύτερος και “παίζει”
Μετά τον 1ο γύρο μένουν οι “2ν-1” με ν = 1, 2, … 1010
Μετά τον 2ο γύρο μένουν οι “4ν-3” με ν = 1, 2, … 505
Μετά τον 3ο γύρο μένουν οι “8ν-7” με ν = 1, 2, … 253
Μετά τον 4ο γύρο μένουν οι “16ν-7” με ν = 1, 2, … 126
Μετά τον 5ο γύρο μένουν οι “32ν-23” με ν = 1, 2, … 63
Μετά τον 6ο γύρο μένουν οι “64ν-55” με ν = 1, 2, … 32 (τελευταίος ο 1993 που “παίζει” και πλήθος επιζώντων 2^5)
Μετά τον 7ο γύρο μένουν οι “128ν-55” με ν = 1, 2, … 16
Μετά τον 8ο γύρο μένουν οι “256ν-55” με ν = 1, 2, … 8
Μετά τον 9ο γύρο μένουν οι “512ν-55” με ν = 1, 2, 3, 4 –> (457 ,969 , 1481 , 1993)
Μετά τον 10ο γύρο μένουν οι “1024ν-55” με ν = 1, 2 –> (969 , 1993)
Μετά τον 11ο γύρο μένει ο “2048ν-55” με ν = 1, δηλαδή ο 1993
Ο 1ος, αφού αυτοί που απομένουν είναι διαδοχικά: 1010, 505, 253, 127, 64, 32, 16, 8, 4, 2, 1.
Λύση:
Αριθμούμε τους συμμετέχοντες από το 1 έως το 2.020. Ξεκινώντας από αριστερά έχουμε:
Στον 1ο γύρο ξεκινά με το μαχαίρι ο 1 και σκοτώνει όλους εκτός από τους 1+2κ, το μαχαίρι καταλήγει σε αυτόν και μένουν 1.010.
Στον 2ο γύρο ξεκινά με το μαχαίρι ο 1 και σκοτώνει όλους εκτός από τους 1+4κ, το μαχαίρι καταλήγει σε αυτόν και μένουν 505.
Στον 3ο γύρο ξεκινά με το μαχαίρι ο 1 και σκοτώνει όλους εκτός από τους 1+8κ, το μαχαίρι καταλήγει στον 1+8=9ο και μένουν 252
Στον 4ο γύρο ξεκινά με το μαχαίρι ο 9ος και σκοτώνει όλους εκτός από τους 9+16κ, το μαχαίρι καταλήγει στον ίδιο και μένουν 126..
Στον 5ο γύρο ξεκινά με το μαχαίρι ο 9ος και σκοτώνει όλους εκτός από τους 9+32κ, το μαχαίρι καταλήγει στον ίδιο και μένουν 63.
Στον 6ο γύρο ξεκινά με το μαχαίρι ο 9ος και σκοτώνει όλους εκτός από τους 9+64κ, το μαχαίρι καταλήγει στον 9+64=73ο και μένουν 31.
Στον 7ο γύρο ξεκινά με το μαχαίρι ο 73ος και σκοτώνει όλους εκτός από τους 73+128κ, το μαχαίρι καταλήγει στον 73+128=201ο και μένουν 15.
Στον 8ο γύρο ξεκινά με το μαχαίρι ο 201ος και σκοτώνει όλους εκτός από τους 201+256κ, το μαχαίρι καταλήγει στον 201+256=457ο και μένουν 7.
Στον 9ο γύρο ξεκινά με το μαχαίρι ο 457ος και σκοτώνει όλους εκτός από τους 457+512κ,
το μαχαίρι καταλήγει στον 457+512=969ο και μένουν 3
Στον 10ο γύρο ξεκινά με το μαχαίρι ο 969ος και σκοτώνει όλους εκτός από τους 969+1.024κ.
το μαχαίρι καταλήγει στον 969+1.024= 1.993ο και έχει μείνει μόνο αυτός!!!
Η λογική λέει ότι για ζυγό αριθμό το μαχαίρι καταλήγει στον αρχικό, ενώ για περιττό αριθμό στον επόμενό του που είναι ζωντανός.
Μερικά ιστορικά στοιχεία για το πως προήλθε αυτό το πρόβλημα.
Το πρόβλημα αυτό ανάγεται στην ρωμαϊκή περίοδό, ήταν πολύ δημοφιλές κατά τη διάρκεια του 15ου και 16ου αιώνα, γνωστό ως το “Πρόβλημα του Ιώσηπου”. Στην γενική εκδοχή του προβλήματος γίνεται αναφορά στην ιστορία μιας ομάδας ανθρώπων ,οι οποίοι επιβαίνουν σε ένα πλοίο και κάποιοι από αυτούς θα πρέπει να θυσιαστούν για να μην βυθιστεί το πλοίο ώστε να σωθούν οι υπόλοιποι. Ανάλογα με την εποχή που διατυπωνόταν το πρόβλημα οι επιβάτες ήταν χριστιανοί η μουσουλμάνοι , σε άλλη εκδοχή ήταν λευκοί οι μαύροι. Τότε ο ήρωας της ιστορίας , προφανώς κάποιος με ευρύ μαθηματικό υπόβαθρο από την μια ομάδα, διέτασσε όλους τους επιβάτες σε ένα κύκλο και ξεκινώντας το μέτρημα από ένα συγκεκριμένο επιβάτη , κάθε ν-οστο άτομο (οπού ν ένας φυσικός αριθμός ) του κύκλου έπεφτε στην θάλασσα .Η διάταξη των επιβατών στον κύκλο γινόταν από τον ηρώα μας με τέτοιο τρόπο ώστε η ομάδα των επιβατών στην όποια ανήκε, είτε οι χριστιανοί , είτε οι λευκοί, επιβίωναν όλοι.
Η πρωτότυπη ιστορία διατυπώνεται για πρώτη φορά από τον Ιώσηπο Φλάβιο ή
Γιοσέφ μπεν Μαθιά (Flavius Josephus 37-100 μ.Χ.), απ’ όπου και πήρε τ’ όνομά του, Εβραίο ιστορικό ο όποιος μετά την πολιορκία και την άλωση, το 67 μ.Χ., της πόλης που διέμενε από τους Ρωμαίους (Ιερουσαλήμ), επέζησε του Ιουδαϊκό-Ρωμαϊκού πολέμου εξαιτίας του μαθηματικού του ταλέντου, όπως ισχυρίζονται πολλοί, και όχι λόγω μιας περίεργης τύχης ή της θείας πρόνοιας, όπως ισχυρίζεται ο ίδιος, κρύφτηκε σε ένα κελάρι μαζί με 40 συμπατριώτες του , οι οποίοι ήταν αποφασισμένοι ν’ αυτοκτονήσουν παρά να πέσουν στα χέρια των Ρωμαίων που τους κατεδίωκαν και να υποβληθούν σε χειρότερα μαρτύρια. Ο Ιώσηπος όμως δεν ήθελε να αυτοκτονήσει , για να σωθεί σκέφτηκε την εξής λύση:
Πρότεινε στους συμπατριώτες του να μπουν σε ένα κύκλο και κάθε τρίτο πρόσωπο του κύκλου να θανατώνεται , μέχρι να πεθάνουν όλοι. Ο Ιώσηπος τοποθέτησε τον εαυτό του και έναν φίλο του αντίστοιχα στις θέσεις 16 και 31 στον κύκλο των 41 ατόμων και έμειναν οι τελευταίοι μετά από τον θάνατο κάθε τρίτου ατόμου ξανά και ξανά , και γλίτωσαν. Πως έλυσε ο Ιώσηπος το πρόβλημα ; Σκέφτηκε αντίστροφα. Αν σχεδιάσουμε ένα κύκλο με 41 μικρούς λευκούς κύκλους . Θεωρούμε ένα κύκλο σαν αφετηρία και ξεκινάμε το μέτρημα, κάθε τρίτο κύκλο τον μαυρίζουμε , συνεχίζουμε το μέτρημα αγνοώντας τους μαυρισμένους κύκλους μέχρι να μείνουν δυο λευκοί κύκλοι . Οι λευκοί κύκλοι βρίσκονται στις θέσεις 16 και 31 από τον κύκλο αφετηρίας.
Ο Ιώσηπος, πιθανότατα, εμπνεύστηκε αυτή την ιδέα, από τον την τιμωρία του Ρωμαϊκού αποδεκατισμου. Όταν ο άνδρες μιας κοόρτης (στρατιωτική μονάδα του Ρωμαικού στρατού σε επίπεδο τάγματος ) σε μια μάχη έδειχναν απροθυμία να πολεμήσουν λόγω δειλίας, ανταρσία, τότε τους τιμωρούσαν με αποδεκατισμό . Οι άνδρες της κοόρτης χωρίζονταν σε δεκάδες και από κάθε δεκάδα με κλήρωση θανατωνόταν φρικτά ο 10ος στρατιώτης.
Ορισμένοι συγγραφείς, όπως οι Τίτος Λίβιος, ο ∆ιονύσιος, ο Πολυβιος κ.α. αναφέρουν σε κείμενα τους συγκεκριμένα περιστατικά και άλλοι μιλούν για ένα γενικότερο έθιμο, μία συνηθισμένη τιμωρία. Το πρώτο κείμενο στο οποίο συναντάμε ένα παρόμοιο πρόβλημα είναι το «De bello Judaico» του Ηγησίου (ψευδόνυμο που μάλλον ανήκει στον Αμβρόσιο του Μιλάνου (370)). Στο κείμενο αυτό αναφέρεται και το γεγονός της σωτηρίας του Ιώσηπου από παρόμοια επιλογή. Παραλλαγές του προβλήματος υπάρχουν σε αρκετά κείμενα του 10ου αιώνα και μετά. Στην Ευρώπη το συναντάμε κυρίως σε χειρόγραφα του 10ου, 11ου και 12ου αιώνα. Στο «Tahbula» του Ραβίνου ben Ezra (1150), ακόμα σε κείμενα του Chuquet (1484) και του Calandri (1500).
Μία από τις πιο γνωστές παραλλαγές του είναι η ακόλουθη:
Οι Τούρκοι και οι Χριστιανοί
Πάνω σε ένα πλοίο που βρισκόταν σε κίνδυνο ήταν 15 Τούρκοι και 15 Χριστιανοί. Έπρεπε να θυσιαστούν οι μισοί έτσι ώστε να επιζήσουν οι υπόλοιποι. Ήταν αναγκαίο η επιλογή να γίνει στην τύχη. Πώς θα έπρεπε να παραταχθούν στον κύκλο έτσι ώστε μετρώντας κάθε 15 άτομα αυτοί που θα θυσιάζονταν να ήταν όλοι Τούρκοι;
Μία εκτεταμένη μελέτη στην ιστορία των προβλημάτων Τούρκων και των Χρι-
στιανών, όπως ονομάζονται, έχει κάνει ο Wilhelm Ahrens (1901). Ο Ahrens δήλωσε ότι ο Cardan είναι ο πρώτος που ονόμασε, στο «Practica Arithmeticae Generalis»
(1539), αυτού του είδους τα προβλήματα «Ludus Josephus». Ακόμα υποστηρίζει ότι το πρόβλημα αυτό υπήρχε στην Ιαπωνία από τον 10ο αιώνα και δημιουργήθηκε εκεί ανεξάρτητα. Ωστόσο το συναντάμε συχνά σε κείμενα του 16ου αιώνα και μετά, όπως των Seki Köwa (1642-1708), Muramatsu Kuday u Moseis (17ο αιώνα) και Miyake Kenryü (18ο αιώνα).
Η Ιαπωνική εκδοχή μιλά για μία μητέρα που καταλάθος αποκλήρωσε τα παιδιά της.
Ο Κληρονόμος
Ένας πλούσιος αγρότης είχε 30 παιδιά, 15 από την πρώτη του σύζυγο που είχε
πεθάνει και 15 από την δεύτερη σύζυγό του. Η τωρινή του σύζυγος ανυπομονού-
σε να πάρει την περιουσία ο μεγαλύτερος γιος της, έτσι κάποια μέρα είπε στον
άντρα της ότι αυτός μεγαλώνει και ότι θα πρέπει να ορίσει τον κληρονόμο του.
Του πρότεινε λοιπόν να βάλουν όλα τα παιδιά σε έναν κύκλο και να εξαιρούν
από την περιουσία κάθε 10ο, έτσι ώστε αυτό που θα έμενε τελευταίο να έπαιρνε
την περιουσία. Η πρόταση αυτή φάνηκε λογική. ́Ομως καθώς η διαδικασία
της επιλογής προχωρούσε ο αγρότης με μεγάλη του έκπληξη παρατήρησε ότι
τα πρώτα 14 παιδιά που εξαιρέθηκαν ήταν από τον πρώτο του γάμο και ότι το
επόμενο θα ήταν το τελευταίο παιδί από τον πρώτο του γάμο. ́Ετσι πρότεινε
από αυτό το παιδί και πέρα να αλλάξουν τη φορά με την οποία μετρούσαν. Η
γυναίκα του σκέφτηκε ότι το ποσοστό ήταν 15 προς 1, με εύνοια προς τα δικά
της παιδιά, και δέχτηκε. Ποιος έγινε τελικά ο κληρονόμος του αγρότη;
W.W.R. Ball and H.S.M. Coxeter, Mathematical Recreations Essays
Λύση:
Τελικά ο κληρονόμος είναι το τελευταίο παιδί από τον πρώτο γάμο. Μάλλον ο αγρότης λεγόταν Ιώσηπος.
Αρχικά αποκλείονται κατά σειρά τα παιδιά:
10,20,30,11,22,3,15,27,9,24,7,23,8,26 Αυτές είναι και οι θέσεις που κατείχαν (σε σειρά από το 1 έως το 30) τα 14 πρώτα παιδιά από τον πρώτο γάμο.
Αν συνεχιστεί η “εξολόθρευση” στο ίδιο μοτίβο (ανά 10) το επόμενο είναι το υπ’ αριθμό 14 (και 15ο υπό εξολόθρευση). Με την αλλαγή όμως το παιδί αυτό γίνεται 1ο στη νέα σειρά των 16 (1,2,..,16) εναπομεινάντων παιδιών και η νέα “εξολόθρευση” πάει (ανά 10) ως εξής: 10,4,15,11,7,5,3,6,9,14,8,2,13,16,12,1 .To 1 λοιπόν (το παλιό 14 και 15ο στην αρχική σειρά) μένει τελευταίο και κερδίζει την κληρονομιά.
Κλασικός αλγόριθμος Josephus.
(Το πρόβλημα του Ιώσηπου στην Ιαπωνία από τον Miyake Kenryü’s Shojutsu Sangaku Zuye(1795), το πρόβλημα της θετής μητέρας)