Το Δίλλημα

Στην αρχαία Ρώμη είναι γνωστό ότι τους αιχμαλώτους πολέμου τους χρησιμοπούσαν για δούλους, για τα λατομεία, για μονομάχους στις αρένες, π.χ. Κολοσσαίο  αφού τους εκπαιδεύανε σε ειδικές σχολές,  είτε μεταξύ τους, είτε με λιοντάρια, για τη ψυχαγωγία τους, ή τους πωλούσαν για σκλάβους. Επίσης, δεν γνωρίζουμε κατά πόσο αληθεύει, αλλά τη μέθοδο αυτή τη χρησιμοποιούσαν για τους στρατιώτες με κάποια παραλλαγή, υπήρχε και η κατωτέρω ψυχαγωγία:
Tοποθετούσαν τους σκλάβους σε ένα μεγάλο κύκλο και έδιναν στον πρώτο ένα μαχαίρι.. Αυτός έπρεπε να σκοτώσει τον διπλανό του και να δώσει το μαχαίρι στον επόμενο. Ο επόμενος θα έκανε το ίδιο και η διαδικασία συνεχιζόταν μέχρι να μείνει μόνο ένας ζωντανός.. Εάν οι σκλάβοι είναι 1.000, ο Lucolus Decius ποια θέση πρέπει να καταλάβει για να είναι ο μοναδικός επιζών; (Κατ. 27/Νο.391)

Πηγή:http://www.youreka.gr/?p=138

Λύση

Ο Lucolus Decius για να είναι ο μοναδικός επιζών πρέπει να καταλάβει την 977η θέση. Ας δούμε το παιχνίδι σε γύρους αριθμώντας τους συμμετέχοντες σκλάβοθς από το 1-1.000 Στον 1ο γύρο ξεκινά με το μαχαίρι ο 1 και σκοτώνει όλους εκτός από τους (1+2κ), το μαχαίρι καταλήγει σε αυτόν και μένουν 500 σκλάβοι. Στον 2ο γύρο ξεκινά με το μαχαίρι ο 1 και σκοτώνει όλους εκτός από τους (1+4κ), το μαχαίρι καταλήγει σε αυτόν και μένουν 250 σκλάβοι. (σκεφτείτε το γιατί γίνεται αυτό!) Στον 3ο γύρο ξεκινά με το μαχαίρι ο 1 και σκοτώνει όλους εκτός από τους (1+8κ), το μαχαίρι καταλήγει σε αυτόν και μένουν 125 σκλάβους. Στον 4ο γύρο ξεκινά με το μαχαίρι ο 1 και σκοτώνει όλους εκτός από τους (1+16κ), το μαχαίρι καταλήγει στον 1+16=17ο και μένουν 62 σκλάβοι. Στον 5ο γύρο ξεκινά με το μαχαίρι ο 17ος και σκοτώνει όλους εκτός από τους (17+32κ), το μαχαίρι καταλήγει στον ίδιο και μένουν 31 σκλάβοι. Στον 6ο γύρο ξεκινά με το μαχαίρι ο 17ος και σκοτώνει όλους εκτός από τους (17+64κ), το μαχαίρι καταλήγει στον 17+64=81ο και μένουν 15 σκλάβοι. Στον 7ο γύρο ξεκινά με το μαχαίρι ο 81ος και σκοτώνει όλους εκτός από τους (81+128κ), το μαχαίρι καταλήγει στον 81+128=209ο και μένουν 7 σκλάβοι. Στον 8ο γύρο ξεκινά με το μαχαίρι ο 209ος και σκοτώνει όλους εκτός από τους (209+256κ), το μαχαίρι καταλήγει στον 209+256=465ο και μένουν 3 σκλάβοι. Στον 9ο γύρο ξεκινά με το μαχαίρι ο 465ος και σκοτώνει όλους εκτός από τους (465+512κ), το μαχαίρι καταλήγει στον 977ο και έχει μείνει μόνο αυτός!!! Η λογική λέει ότι για ζυγό αριθμό το μαχαίρι καταλήγει στον αρχικό, ενώ για περιττό αριθμό στον επόμενό του που είναι ζωντανός. Διευκρίνιση: Ένα πολύ γνωστό πρόβλημα που ανάγεται στην ρωμαϊκή περίοδό. Ο Ιώσηπος Φλάβιος (Titus Flavius Iosephus) πιθανότατα εμπνεύστηκε αυτό το γρίφο από την τιμωρία του ρωμαϊκού αποδεκατισμου. Όταν ο άνδρες μιας κοόρτις (στρατιωτική μονάδα του Ρωμαικού στρατού σε επίπεδο τάγματος ) σε μια μάχη έδειχναν απροθυμία να πολεμήσουν ή δειλία, τότε τους τιμωρούσαν με αποδεκατισμό . Οι άνδρες της κοόρτις χωρίζονταν σε δεκάδες και από κάθε δεκάδα με κλήρωση θανατωνόταν φρικτά ένας στρατιώτης με ρόπαλα. Λύση του Γ. Ριζόπουλου. Τέτοιου τύπου αλγοριθμικά προβλήματα καλούνται στη γενική μορφή τους "Πρόβλημα του Ιώσηπου". Από τον εβραιορωμαίο λόγιο Ιώσηπο Φλάβιο,που αναφέρει μια παραλλαγή. Κάθε δύναμη του 2 αφήνει νικητή τον πρώτο (αυτόν που ξεκινάει τον κύκλο του θανάτου). Γενικά: 2*(1.000-2^(floor(log2(1.000)))+1=977 Η θέση 977 επιζεί... Σημείωση: Το floor(log2(1.000)) είναι το ακέραιο μέρος του λογαρίθμου βάσης 2 του 1.000. (=9) Διευκρίνιση: Ο μοναδικός επιζών πρέπει να πάρει την αμέσως προηγούμενη θέση: [1+(2*1.000)-2^10]=1+2.000-1.024=2.001-1.024=977 Ένα άλλο τρικ που λύνει το πρόβλημα για τυχαίο πλήθος ν και βήμα 2,είναι η μετατροπή του ν σε δυαδικό αριθμό: ν=1.000(10) --->1111101000(2) Μετάθεση του πρώτου αριστερά άσσου στα δεξιά 1111101000(2) ---->1111010001(2) ,δυαδικός αριθμός που στο δεκαδικό είναι: 1111010001(2) =997(10).