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

Μαρτίου 12, 2008

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

Filed under: Λυμένα Προβλήματα,Με υπόδειξη — Mihalis Kolountzakis @ 10:08 πμ

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

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

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

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

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

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

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

Advertisements

9 Σχόλια »

  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 μμ

  4. Θα πρέπει το μήκος τους να είναι μικρότερο του n, καθώς σε έναν κύκλο με μήκος > n κάποιοι δε θα φτάσουν ποτέ τον αριθμό τους.
    Η πιθανότητα να υπάρχει κύκλος, K, μήκους m > n ισούται με
    \binom{2n}{m}\frac{m-1}{2n}\frac{m-2}{2n-1}\cdots\frac{m-(m-1)}{2n-m+2}\frac{1}{2n-m+1} = 1/m
    και συνεπώς η πιθανότητα να υπάρχει κύκλος μήκους > n ισούται με
    \sum_{k=n+1}^{2n}\frac{1}{m}\approx\int_{n+1}^{2n}=\ln2

    Μου αρέσει!

    Σχόλιο από henk&christos — Απρίλιος 30, 2010 @ 8:07 μμ

  5. λείπει το 1/x dx μετά το ολοκλήρωμα

    Μου αρέσει!

    Σχόλιο από henk&christos — Απρίλιος 30, 2010 @ 8:10 μμ

  6. Με συγχωρείτε. Τα έκανα θάλασσα. Το ξαναγράφω:
    \sum_{k=n+1}^{2n}\frac{1}{k}\approx\int_{n}^{2n}\frac{1}{x}=\ln2

    Μου αρέσει!

    Σχόλιο από henk&christos — Απρίλιος 30, 2010 @ 8:14 μμ

  7. Πολύ σωστά.

    Πρέπει να γίνει η παρατήρηση ότι στο άθροισμα \sum_{k=n+1}^{2n}\frac{1}{k}\approx\int_{n}^{2n}\frac{1}{x}=\ln2 μπορείς και προσθέτεις τις πιθανότητες επειδή τα ενδεχόμενα είναι ανά δύο ξένα: δεν είναι δυνατό να έχουμε δύο κύκλους μήκους >n. Φυσικά, αν κανείς δεν το παρατηρήσει αυτό και γράψει απλά ότι η πιθανότητα είναι το πολύ τόσο δεν πειράζει αφού το μόνο που θέλουμε είναι να φράξουμε αυτή την πιθανότητα προς τα πάνω.

    Όμως καλό θα ήτανε να μας εξηγήσεις το γιατί είναι η πιθανότητα να έχουμε κύκλο μήκους m ίση με
    \binom{2n}{m}\frac{m-1}{2n}\frac{m-2}{2n-1}\cdots\frac{m-(m-1)}{2n-m+2}\frac{1}{2n-m+1}.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Μαΐου 1, 2010 @ 9:03 μμ

  8. Ξεκινούμε από κάποιο τυχαίο κουτί, π.χ., το b_1 και ακολουθούμε τη μετάθεση.
    Η πιθανότητα, p_m, να ακολουθήσουμε κύκλο μήκους m είναι ίση με την πιθανότητα
    b_2:=\tau(b_1) να μην είναι το b_1 και b_3:=\tau(b_2) να μην είναι το b_1 και … και b_{m-1}:=\tau(b_{m-2}) δεν είναι το b_1 αλλά b_{m}:=\tau(b_{m-1}) είναι το b_1 . Η πιθανότητα αυτή ισούται με
    \frac{m-1}{2n} \frac{m-2}{2n-1} \cdots \frac{m-(m-1)}{2n-m+2} \frac{1}{2n-m+1}.
    Η πιθανότητα να υπάρχει κύκλος μήκους m υπολογίζεται αθροίζοντας τα p_m πάνω απ’όλα τα υποσύνολα του \left\{1,2,\cdots, 2n\right\} πλήθους m.

    Μου αρέσει!

    Σχόλιο από henk&christos — Μαΐου 2, 2010 @ 12:37 πμ

  9. Σωστά.

    Εγώ θα το έλεγα ως εξής: η πιθανότητα να υπάρχει κύκλος μήκους ακριβώς m είναι το άθροισμα των πιθανοτήτων πάνω από όλα τα υποσύνολα μεγέθους m το να είναι το συγκεκριμένο υποσύνολο κύκλος (αυτό ισχύει όταν m>n επειδή ακριβώς δεν μπορούν να υπάρχουν δύο τέτοιοι κύκλοι και άρα τα ενδεχόμενα είναι ξένα και μπορούμε να τα προσθέσουμε). Αν έχουμε σταθεροποιήσει κάποια m στοιχεία τότε πόσες μεταθέσεις των 1\ldots 2n υπάρχουν που να είναι αυτά τα στοιχεία κύκλος; Οι κυκλικές μεταθέσεις αυτών των m στοιχείων είναι το πλήθος (m-1)! και οι οποιεσδήποτε μεταθέσεις των υπολοίπων ανάμεσά τους είναι (2n-m)!. Άρα η πιθανότητα είναι \frac{(m-1)!(2n-m)!}{(2n)!}. Πολλαπλασιάζουμε αυτό με {2n \choose m} (το πλήθος των τρόπων να επιλέξουμε τα m αυτά στοιχεία και παίρνουμε το ζητούμενο 1/m.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Μαΐου 2, 2010 @ 10:43 πμ


RSS feed for comments on this post. TrackBack URI

Σχολιάστε

Συνδεθείτε για να δημοσιεύσετε το σχόλιο σας:

Λογότυπο WordPress.com

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό WordPress.com. Αποσύνδεση / Αλλαγή )

Φωτογραφία Twitter

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Twitter. Αποσύνδεση / Αλλαγή )

Φωτογραφία Facebook

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Facebook. Αποσύνδεση / Αλλαγή )

Φωτογραφία Google+

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Google+. Αποσύνδεση / Αλλαγή )

Σύνδεση με %s

Blog στο WordPress.com.

Αρέσει σε %d bloggers: