Προβλήματα Μαθηματικών

Μαρτίου 12, 2008

Στρατηγική απελευθέρωσης

Κατηγορίες: Άλυτα Προβλήματα, Με υπόδειξη — Mihalis Kolountzakis @ 10:08 πμ

Σε μια φυλακή υπάρχουν 2n βαρυποινίτες (n μεγάλο).
Ο διευθυντής της φυλακής αποφασίζει να παίξει ένα σκληρό παιχνίδι μαζί τους:

Σ’ ένα δωμάτιο μέσα υπάρχουν 2n κλειστά κουτιά και μέσα στα κουτιά υπάρχουν τα ονόματα των 2n κρατουμένων, ένα όνομα σε κάθε κουτί, σε θέσεις που είναι άγνωστες στους κρατουμένους. Οι κρατούμενοι μπαίνουν ένας-ένας μέσα στο δωμάτιο, μόνοι τους, και ανοίγουν n κουτιά, τα οποία επιλέγουν αυτοί. Αν μέσα στα n αυτά κουτιά υπάρχει το όνομα του κρατουμένου που τα ανοίγει τότε αυτός, αφού ξανακλείσει όλα τα κουτιά χωρίς να πειράξει τα περιεχόμενά τους, βγαίνει έξω και μπαίνει ο επόμενος.

Αν βγει έξω και ο τελευταίος τότε όλοι οι κρατούμενοι απελευθερώνονται.

Αν όχι τότε το παιχνίδι σταματάει και όλοι οι κρατούμενοι εκτελούνται.

Οι κρατούμενοι μπορούν να συννενοηθούν για το ποια στρατηγική θα ακολουθήσουν πριν αρχίσει το παιχνίδι αλλά απαγορεύεται να ανταλλάξουν οποιαδήποτε πληροφορία αφού αρχίσει το παιχνίδι.

Είναι φανερό ότι αν κάθε κρατούμενος μπει μέσα και ανοίξει n κουτιά στην τύχη τότε η πιθανότητα να βρεί το δικό του όνομα είναι 1/2, άρα η πιθανότητα να επιζήσουν οι κρατούμενοι, αν παίζουν με αυτό τον τρόπο, είναι 2^{-n}, που πηγαίνει στο 0 απελπιστικά γρήγορα.

Δείξτε ότι οι κρατούμενοι μπορούν να επιλέξουν να παίξουν με μια στρατηγική που τους εγγυάται πιθανότητα επιβίωσης η οποία δε συγκλίνει στο 0 με το n \to \infty.

3 σχόλια »

  1. Υπόδειξη:

    Κατ’αρχήν οι κατάδικοι, πριν αρχίσουν να παίζουν το παιχνίδι, ρίχνουν τα ζάρια τους και δίνουν στα κουτιά μια τυχαία ονομασία: το κουτί Νο 1 θα λέγεται στο εξής \pi_1, το κουτί Νο 2 θα λέγεται \pi_2, κοκ. (Οι αριθμοί \pi_1, \pi_2, \ldots, \pi_{2n} είναι μια τυχαία μετάθεση των αριθμών 1, 2, \ldots, 2n.) Ο λόγος που το κάνουν αυτό είναι ώστε να μη μπορεί κανείς να καθορίσει τα περιεχόμενα που αντιστοιχούν στο \nu-οστό κουτί με τρόπο ώστε να αποτύχει η μέθοδός τους (η περιγραφή της οποίας ακολουθεί).

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

    Κάθε ένας που πάει μέσα κάνει το εξής. Αν το όνομα του καταδίκου είναι \nu (οι κατάδικοι έχουν τα ονόματα 1,\ldots, 2n) τότε πάει και ανοίγει το κουτί \pi_{\nu}. Αν βρεί μέσα το όνομά του έχει καλώς, σταματάει και βγαίνει έξω. Αλλιώς, αν το περιεχόμενο είναι ο αριθμός k πάει και ανοίγει το κουτί \pi_k. Και πάλι αν βρεί μέσα το όνομά του έχει καλώς και σταματάει, αλλιώς συνεχίζει και πηγαίνει στο κουτί που του λέει το περιεχόμενο του \pi_k. Αυτό συνεχίζεται μέχρι να βρει το όνομά του ή μέχρι να ανοίξει n κουτιά. Αν συμβεί το τελευταίο και δεν έχει βρει το όνομά του τότε το παιχνίδι τελειώνει εις βάρος των καταδίκων, αλλιώς μπαίνει ο επόμενος.

    Βρείτε τι πιθανότητα επιτυχίας έχουν αν παίζουν με αυτό τον τρόπο.

    Ένας τρόπος να το σκεφτείτε είναι να δείτε την όλη κατάσταση ως μια μετάθεση

    \tau = \left( \begin{array}{llll} \pi_1 & \pi_2 & \ldots & \pi_{2n}\\ \alpha & \beta & \ldots & \omega \end{array} \right)

    όπου στην πάνω γραμμή είναι τα ονόματα των κουτιών και κάτω είναι τα περιεχόμενά τους. Η μετάθεση \tau είναι μια τυχαία μετάθεση (εξίσου πιθανό να είναι κάθε μια από τις μεταθέσεις της S_{2n}).

    Σχόλιο από Mihalis Kolountzakis — Ιουλίου 1, 2008 @ 8:56 πμ

  2. Με τον τροπο που περιγραφεις ο μοναδικος τροπος για να εκτελεστουν οι κρατουμενοι ειναι αν η παραπανω μεταθεση ειναι μια διατάραξη δηλαδη κανενα στοιχειο να μην παραμενει στην θεση του. Σε μια τυχαια μεταθεση n στοιχείων η πιθανότητα να ειναι διατάραξη καθως το n τείνει στο απειρο ειναι 1/e

    Σχόλιο από mcdallas — Ιουνίου 24, 2009 @ 7:52 μμ

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

    Σχόλιο από Mihalis Kolountzakis — Ιουνίου 24, 2009 @ 8:48 μμ


Κανάλι RSS για τα σχόλια του άρθρου. TrackBack URI

Γράψτε ένα σχόλιο

Για να σχολιάσετε πρέπει να συνδεθείτε.

Blog στο WordPress.com.