Μαθη...μαγικά : Πρέπει να μείνει μόνο ένας.Το πρόβλημα του Ιώσηπου.

Σάββατο 23 Ιουλίου 2011

Πρέπει να μείνει μόνο ένας.Το πρόβλημα του Ιώσηπου.

'Άιντε, ένα χεράκι ακόμη και τη βγάλαμε τη ζωή… Να πάρουν σειρά οι άλλοι.”

Μενέλαος Λουντέμης

Ένα πολύ γνωστό πρόβλημα που ανάγεται στην Ρωμαϊκή περίοδο είναι το πρόβλημα του Ιώσηπου. Στην γενική εκδοχή του προβλήματος γίνεται αναφορά στην ιστορία μιας ομάδας ανθρώπων,οι οποίοι επιβαίνουν σε ένα πλοίο και κάποιοι από αυτούς θα πρέπει να θυσιαστούν για να μην βυθιστεί το πλοίο ώστε να σωθούν οι υπόλοιποι.

Ανάλογα με την εποχή που διατυπωνόταν το πρόβλημα οι επιβάτες ήταν χριστιανοί η μουσουλμάνοι,σε άλλη εκδοχή ήταν λευκοί οι μαύροι.Τότε,ο ήρωας της ιστορίας,από την μια ομάδα,διέτασσε όλους τους επιβάτες σε ένα κύκλο και ξεκινώντας το μέτρημα από ένα συγκεκριμένο επιβάτη,κάθε ν-οστο άτομο (οπού ν ένας φυσικός αριθμός)του κύκλου έπεφτε στην θάλασσα.Η διάταξη των επιβατών στον κύκλο γινόταν από τον ήρωα μας με τέτοιο τρόπο ώστε η ομάδα των επιβατών στην όποια ανήκε,είτε οι χριστιανοί,είτε οι λευκοί,επιβίωναν όλοι.

Η πρωτότυπη ιστορία διατυπώνεται για πρώτη φορά από τον Ιώσηπο Φλάβιο,Εβραίο ιστορικό ο όποιος μετά την πολιορκία και την άλωση της πόλης που διέμενε από τους Ρωμαίους, κρύφτηκε σε ένα κελάρι μαζί με 40 συμπατριώτες του,οι οποίοι ήταν αποφασισμένοι να αυτοκτονήσουν παρά να πέσουν στα χέρια των Ρωμαίων που τους κατεδίωκαν και να υποβληθούν σε χειρότερα μαρτύρια. Ο Ιώσηπος όμως δεν ήθελε να αυτοκτονήσει,για να σωθεί σκέφτηκε το εξής κόλπο.Πρότεινε στους συμπατριώτες του να μπουν σε ένα κύκλο και κάθε τρίτο πρόσωπο του κύκλου να θανατώνεται,μέχρι να πεθάνουν όλοι.Ο Ιώσηπος τοποθέτησε τον εαυτό του και έναν φίλο του αντίστοιχα στις θέσεις 16 και 31 στον κύκλο των 41 ατόμων και έμειναν οι τελευταίοι μετά από τον θάνατο κάθε τρίτου ατόμου ξανά και ξανά,και γλίτωσαν.

Ο Ιώσηπος πιθανότατα εμπνεύστηκε το κόλπο,από τον την τιμωρία του ρωμαϊκού αποδεκατισμου . Όταν οι άνδρες μιας κοορτης (στρατιωτική μονάδα του Ρωμαικού στρατού σε επίπεδο τάγματος ) σε μια μάχη έδειχναν απροθυμία να πολεμήσουν,δειλία,τότε τους τιμωρούσαν με αποδεκατισμό.Οι άνδρες της κοορτής χωρίζονταν σε δεκάδες και από κάθε δεκάδα με κλήρωση θανατωνόταν φρικτά ένας στρατιώτης.

Πως έλυσε ο Ιώσηπος το πρόβλημα;
Αν σχεδιάσουμε ένα κύκλο με 41 μικρούς λευκούς κύκλους.Θεωρούμε ένα κύκλο σαν αφετηρία και ξεκινάμε το μέτρημα,κάθε τρίτο κύκλο τον μαυρίζουμε,συνεχίζουμε το μέτρημα αγνοώντας τους μαυρισμένους κύκλους μέχρι να μείνουν δυο λευκοί κύκλοι .Οι λευκοί κύκλοι βρίσκονται στις θέσεις 16 και 31 από τον κύκλο αφετηρίας.

Από ιαπωνική έκδοση μαθηματικών προβλημάτων του 1795

Το πρόβλημα του Ιώσηπου το πέτυχα ξανά σε μια ομάδα στο facebooκ ελαφρώς τροποποιημένο.

Έχουμε 2018 ανθρώπους σε ένα κύκλο όπου κάθε δεύτερο πρόσωπο πεθαίνει μέχρι να μείνει ένας. Δηλαδή, ο πρώτος σκοτώνει τον δεύτερο ο τρίτος τον τέταρτο ,ο πέμπτος τον έκτο κ.ο.κ μέχρι να μείνει ένας. Ποιος θα μείνει;

Ας κάνουμε τους υπολογισμούς με τα παρακάτω σχήματα για 4 ανθρώπους .

Φυσικά από ένα παράδειγμα είναι δύσκολο να αναγνωρίσουμε μοτίβο και να γενικεύσουμε για ν ανθρώπους. Ας δοκιμάσουμε για περισσότερους ανθρώπους,κατασκευάζουμε ένα πινάκα:

Ν άνθρωποι Επιζών

2 1^ος

3 3^ος

4 1^ος

5 3^ος

6 5^ος

7 7^ος

8 1^ος

9 3^ος

10 5^ος

11 7^ος

12 9^ος

13 11^ος

14 13^ος

15 15^ος

16 1^ος

Τι παρατηρούμε; Σε κάθε γύρο σκοτώνονται οι μισοί δηλαδή το πλήθος υποδιπλασιάζεται άρα είναι λογικό όταν μετά από κάθε πέρασμα το πλήθος των ανθρώπων είναι άρτιο, ο 1^ος θα επιβιώνει.Πότε μετά από κάθε πέρασμα το πλήθος είναι άρτιο;Όταν το συνολικό πλήθος είναι δύναμη του 2.
Συνεπώς,αν το συνολικό πλήθος είναι δύναμη του 2 ,ο 1^ος πάντα θα επιβιώνει. Δηλαδή όταν έχουμε ένα κύκλο με πλήθος δύναμη του 2 θα επιβιώσει ο πρώτος τον κύκλο. (Φαίνεται και στον πίνακα)

Το ερώτημα είναι τι συμβαίνει όταν δεν έχουμε δύναμη του 2;

Όταν σε κάποιο πέρασμα το πλήθος των εναπομενόντων γίνει περιττό, στην αρχή του επομένου περάσματος ο 1^ος θα πεθάνει. Μετά από κάποιο πέρασμα κάποια στιγμή οι εναπομείναντες θα είναι δύναμη του 2 τότε το πρώτο πρόσωπο σε αυτόν κύκλο θα είναι αυτός που θα επιβιώσει.
Πως θα βρούμε τώρα το πρώτο πρόσωπο σε αυτόν το κύκλο;

Δείτε τι συμβαίνει όταν έχουμε 9 άτομα.

Μετά το πρώτο πέρασμα έμειναν: ο 3^ος ,5^ος ,7^ος και ο 9^ος ,πλήθος 4 που είναι δύναμη του 2 άρα ο πρώτος στον κύκλο (ο 3^ος) θα επιβιώσει όπως και συμβαίνει.

Ας το γενικεύσουμε. Έστω ότι το πλήθος Ν των ανθρώπων, δεν είναι δύναμη του 2 άρα γράφεται:

Ν=2^κ+λ όπου λ μικρότερο από 2^κ

Θα πρέπει να εξαλειφτούν οι λ άνθρωποι για να μείνει δύναμη του 2 ,οι λ άνθρωποι θα εξαλειφτούν μετά από ένα πέρασμα 2λ ανθρώπων ετσι ο 2λ+1 θα είναι αυτός που θα επιβιώσει.

Συνοψίζουμε,

-Αν το πλήθος Ν των ανθρώπων του κύκλου είναι δύναμη του 2 τότε επιβίωνε ο πρώτος στον κύκλο.

-Αν το πλήθος Ν των ανθρώπων του κύκλου δεν είναι δύναμη του 2 βρίσκουμε την δύναμη του 2 που δεν το ξεπερνά έστω 2^Κ τότε επιβιώνει ο 2(Ν-2^κ)+1 στον κύκλο.

Για παράδειγμα, σε κύκλο 2018 ατόμων υπολογίζουμε την δύναμη του 2 που δεν ξεπερνά το 2018 είναι 2¹⁰=1024 σύμφωνα με τα παραπάνω θα επιβιώσει ο 2*(2018-1024)+1=1989^ος

Ένα συναφές πρόβλημα
http://mathhmagic.blogspot.gr/2013/04/blog-post_1045.html
Μια προσομοίωση του προβλήματος
http://yooksel.com/Josephus-Problem/