JotD / QotD Ελληνική Λίστα Κουίζ (QotD)


Θέμα: Re: Quiz...ΛΥΣΗ στο"100φυλακισμένοι και1λάμπα"



(nil): Vaggelis Kapoulas (kapoulas(@)cti.gr)
Ημερομηνία: Tue 17 Sep 2002 - 10:46:08 EEST

Γεια και χαρά,

Ηρθε ο καιρός για να ανακοινωθεί η λύση (ή μάλλον μερικές
σωστές λύσεις) για το πρόβλημα. Πριν όμως από τις λύσεις
ας θυμηθούμε το πρόβλημα:

Vaggelis Kapoulas wrote:
>
> Μία φυλακή έχει 100 φυλακισμένους σε κελιά απομόνωσης (δηλαδή
> οι φυλακισμένοι δεν επικοινωνούν μεταξύ τους με κανένα τρόπο).
>
> Επίσης έχει ένα δωμάτιο στο οποίο υπάρχει μία λάμπα.
>
> Ο διευθυντής αποφασίζει να δώσει στους φυλακισμένους την εξής
> ευκαιρία να αποφυλακιστούν:
>
> Κάθε μέρα ένας από τους φυλακισμένους που θα επιλέγεται τυχαία
> (με ομοιόμορφη κατανομή) θα οδηγείται στο δωμάτιο με τη λάμπα
> και εκεί θα μπορεί να την ανάψει (αν είναι σβηστή) ή να τη
> σβήσει (αν είναι αναμένη) ή να μην την πειράξει καθόλου
> (δηλαδή να την αφήσει στην κατάσταση που τη βρήκε).
>
> Επίσης ο φυλακισμένος θα μπορεί, εάν θέλει, να ισχυριστεί οτι
> όλοι οι φυλακισμένοι έχουν οδηγηθεί (τουλάχιστον μία φορά) στο
> δωμάτιο μέχρι εκείνη τη στιγμή.
>
> Εάν ο ισχυρισμός του είναι σωστός, τότε απελευθερώνονται όλοι
> οι φυλακισμένοι (και τους δίνονται υψηλόβαθμες θέσεις καθώς
> όλοι θέλουν έξυπνους ανθρώπους σε αυτές ;-)
>
> Εάν ο ισχυρισμός του είναι λανθασμένος, τότε όλοι οι κρατούμενοι
> εκτελούνται (για τη βλακεία τους, που ο διευθυντής δεν συγχωρεί).
>
> Κανείς φυλακισμένος δεν μπορεί να δει ποιος οδηγείται στο
> δωμάτιο ή τι κάνει με τη λάμπα.
>
> Ο διευθυντής επιτρέπει στους φυλακισμένους να συναντηθούν
> μία φορά, όλοι μαζί, πριν την έναρξη της διαδικασίας για
> να αποφασίσουν τη στρατηγική τους.
>
> Σε τι πλάνο πρέπει να συμφωνήσουν οι φυλακισμένοι έτσι ώστε να
> είναι βέβαιο ότι κάποια στιγμή κάποιος θα μπορέσει να ισχυριστεί
> σωστά οτι όλοι έχουν περάσει από το δωμάτιο;

Υπάρχουν αρκετές λύσεις. Στη συνέχεια θα παρουσιάσω τρεις, αλλά
μπορεί να υπάρχουν και άλλες που δεν γνωρίζω.

1η λύση (φοβερά αργή)
---------------------

Η λύση όπως την έστειλε ο Damianos Karakos

Damianos Karakos wrote:
>
> Geia sou Baggelh,
>
> endiaferon to quiz sou. Na mia lysh pou skefthka
> (isxyei gia N kratoumenous):
>
> Kata thn arxikh synanthsh olwn twn kratoumenwn:
> a) Dinoun noumera ston ka0ena, 0, 1, ..., N-1.
> b) Xwrizoun to xrono se synexomena blocks twn N hmerwn.
> H strathgikh tous einai:
> c) An o kratoumenos no. 0 mpei sto dwmatio th mera
> j*N, gia kapoio j >= 0 (dhl. thn 1h mera enos
> opoiodhpote block) tote anabei th lamba (an den einai
> hdh anamenh).
> d) An o kratoumenos no. k mpei sto dwmatio th mera j*N + l
> kai k != l, tote sbhnei th lamba (an einai anamenh).
> e) An o kratoumenos no. k mpei sto dwmatio th mera j*N + k,
> (kai k > 0) tote afhnei th lamba opws htan.
> f) An o kratoumenos no. N-1 mpei sto dwmatio th mera j*N + N-1
> kai h lamba einai anamenh, tote isxyrizetai oti oloi
> oi kratoumenoi exoun odhgh0ei sto dwmatio toulaxiston
> mia fora.
>
> O parapanw algori0mos eggyatai oti o kratoumenos no. N-1 0a
> brei anamenh th lamba monon otan oloi oi kratoumenoi
> exoun episkey0ei to dwmatio me th seira, tis N-1 prohgoumenes
> meres.
>
> Oi episkepseis twn fylakismenwn einai anejarthtes. Oi kratoumenoi
> eley0erwnontai mono otan se ena block twn N hmerwn exoun paei
> me th seira 0, 1, ..., N-1 sto dwmatio. H pi0anothta na ginei
> ayto einai (1/N)^N. Se ayth thn periptwsh to block 0ewreitai
> epityxes. H pi0anothta apotyxias enos block einai
> 1 - (1/N)^N. Ta blocks einai anejarthta opote an 0ewrhsoume
> tis epityxies/apotyxies twn blocks ws Bernoulli trials,
> briskoume telika oti h mesh timh twn blocks mexri thn epityxia
> einai N^N (symperilambanomenhs kai ths teleytaias). Opote,
> afou ka0e block exei N meres, h mesh timh twn hmerwn
> einai N^(N+1).
>
> O algori0mos mallon den einai o beltistos dynatos giati
> den lambanei yp'opshn oti oi kratoumenoi exoun mnhmh kai mporoun
> na anapsoun thn lamba kai se alles periptwseis (xwris na
> xreiastei na perimenoun thn arxh tou epomenou block se periptwsh
> pou ginei mia apotyxia). P.x. o kratoumenos k mporei na anapsei
> th lamba th mera j*N + l, an eixe episkey0ei to dwmatio sto
> parel0on mia mera m*N + n kai brhke th lamba anamenh (opou
> m < j kai n > l).

2η λύση
-------

Η λύση όπως την έστειλε ο George Papargiris

> Γενική περιγραφή της λύσης
>
> Ένας από τα 100 άτομα θα είναι ο αρχηγός της ομάδας ενώ οι
> υπόλοιποι 99 θα είναι τα μέλη. Κάθε ένα από τα μέλη θα ανάψει
> μία φορά ακριβώς τη λάμπα. Η λάμπα σβήνεται μόνο από τον αρχηγό
> ο οποίος κάνει και τη μέτρηση για το πόσα άτομα έχουν περάσει
> από το δωμάτιο. Κάθε μέλος ανάβει τη λάμπα μόνο την πρώτη φορά
> που μπαίνει στο δωμάτιο και μόνο στην περίπτωση που τη βρει
> σβηστή. Αν τη βρει αναμένη δεν την πειράζει γιατί την έχει
> ανάψει κάποιος άλλος του οποίου η παρουσία καταμετράται από
> τον αρχηγό. Για να κερδίσουν όσο το δυνατό περισσότερες μέρες
> βολεύει ο αρχηγός να είναι αυτός που είναι δυνατό να σβήσει
> γρηγορότερα τη λάμπα δηλαδή αυτός που θα επιλεγεί τη δεύτερη
> μέρα (ακόμα κι αν είναι ο ίδιος με αυτόν που επιλέχτηκε την
> πρώτη μέρα).
>
> Αναλυτικά ο αλγόριθμος είναι ο εξής:
>
> Ο πρώτος που μπαίνει στο δωμάτιο ανάβει τη λάμπα αν είναι
> σβηστή. Αν τη βρει αναμένη την αφήνει όπως είναι αφού κάθε
> κατάσταση της λάμπας έχει συγκεκριμένο νόημα και μια λάθος
> αρχικοποιήση του προβλήματος θα τα τινάξει όλα στον αέρα.
>
> Αυτός που μπαίνει τη δεύτερη μέρα (μπορεί να είναι και αυτός
> που μπήκε την πρώτη μέρα) γίνετε αρχηγός. Δεν πειράζει που δεν
> ξέρουν οι άλλοι ποιος είναι. Ο ρόλος του είναι συγκεκριμένος.
> Ξέρει ότι ένας έχει ήδη περάσει από το δωμάτιο οπότε βάζει στο
> μετρητή την αρχική τιμή 1 και σβήνει τη λάμπα.
>
> Για τις υπόλοιπες φορές κάθε μέλος όταν μπει στο δωμάτιο με τη
> λάμπα λειτουργεί ως εξής: αν η λάμπα είναι σβηστή και δεν την
> έχει ανάψει ο ίδιος στο παρελθόν τότε την ανάβει. Σε κάθε άλλη
> περίπτωση (δηλαδή αν η λάμπα είναι αναμμένη ή αν είναι σβηστή
> αλλά ο ίδιος την έχει ανάψει ξανά στο παρελθόν) τότε δεν την
> πειράζει.
>
> Ο αρχηγός λειτουργεί ως εξής: Κάθε φορά (από τη στιγμή που θα
> αναλάβει τα καθήκοντά του) που βλέπει τη λάμπα αναμμένη, τη
> σβήνει και αυξάνει κατά 1 το μετρητή που λέει πόσοι κρατούμενοι
> έχουν μπει στο δωμάτιο. Αν η λάμπα είναι σβηστή δεν την πειράζει.
> Στην περίπτωση που ο αρχηγός είναι αυτός που μπήκε και την πρώτη
> μέρα , μόλις ο μετρητής του φτάσει στο 100 ανακοινώνει ότι όλοι
> έχουν περάσει τουλάχιστο μια φορά από το δωμάτιο. Αν ο αρχηγός
> δεν είναι αυτός που μπήκε και την πρώτη μέρα στο δωμάτιο κάνει
> την ανακοίνωση όταν ο μετρητής φτάσει στο 99.

Στην λύση αυτή ο αρχηγός λειτουργεί ως καταμετρητής των φυλακισμένων
που έχουν ήδη περάσει από το δωμάτιο.

Ο George Papargiris υπολόγισε και το μέσο όρο των ημερών που
χρειάζονται, και είναι περίπου 10320.

3η λύση
-------

Για να επιταχυνθεί η διαδικασία καταμέτρησης μπορούμε να έχουμε
περισσότερους καταμετρητές.

Η τρίτη λύση χωρίζει τη στρατηγική των φυλακισμένων σε φάσεις:
Φάση 1: Οι μισοί φυλακισμένοι λειτουργούν ως αρχηγοί (δηλαδή,
        καταμετρητές) και καταμετρούν μέχρι 2 παρουσίες
        φυλακισμένων στο δωμάτιο (του ιδίου και ενός άλλου).
        Για να επιταχυνθεί η διαδικασία, οι καταμετρητές δεν
        ορίζονται από την αρχή, αλλά κάθε φυλακισμένος, αν
        βρεί τη λάμπα αναμμένη γίνεται καταμετρητής, αλλιώς
        ανάβει τη λάμπα και αφήνει άλλον να καταμετρήσει την
        παρουσία του.
Φάση 2: Στη φάση 2 συμμετέχουν μόνο οι καταμετρητές της φάσης
        1. Οι καταμετρητές αυτοί έχουν καταμετρήσει 2 παρουσίες
        ο καθένας. Φυσικά, μπορεί να υπάρχουν και φυλακισμένοι
        που δεν έχουν περάσει από το δωμάτιο, αλλά με αυτούς θα
        ξανα-ασχοληθούμε προς το τέλος. Η φάση είναι παρόμοια με
        τη φάση 1. Καταμετρητές αυτής της φάσης είναι πάλι οι
        μισοί από τους εμπλεκόμενους. Στη φάση αυτή το άναμμα
        της λάμπας μετράει για 2 και κάθε καταμετρητής μετράει
        μέχρι 4 παρουσίες (2 που είχε από την φάση 1 και άλλες
        2 που καταμετρά στη φάση 2, βρίσκοντας μία φορά αναμμένη
        τη λάμπα).
Φάση 3: Στη φάση 3 συμμετέχουν μόνο οι καταμετρητές της φάσης
        2. Οι καταμετρητές αυτοί έχουν καταμετρήσει 4 παρουσίες
        ο καθένας. Φυσικά, μπορεί να υπάρχουν και φυλακισμένοι
        που δεν πρόλαβαν να λάβουν μέρουν μέρος στη φάση 2,
        αλλά, όπως και πριν, με αυτούς θα ξανα-ασχοληθούμε προς
        το τέλος. Η φάση είναι παρόμοια με τις φάσεις 1 και 2.
        Καταμετρητές αυτής της φάσης είναι πάλι οι μισοί από
        τους εμπλεκόμενους. Στη φάση 3 το άναμμα της λάμπας
        μετράει για 4 και κάθε καταμετρητής μετράει μέχρι 8
        παρουσίες (4 που είχε από την φάση 2 και άλλες
        4 που καταμετρά στη φάση 3, βρίσκοντας, και πάλι, μία
        φορά αναμμένη τη λάμπα).
Φάση 4: Στη φάση 4 συμμετέχουν ο αρχηγός και οι καταμετρητές
        της φάσης 3. Οι καταμετρητές αυτοί έχουν καταμετρήσει
        8 παρουσίες ο καθένας. Φυσικά, μπορεί να υπάρχουν και
        φυλακισμένοι που δεν πρόλαβαν να λάβουν μέρουν μέρος
        στη φάση 3, αλλά, όπως και πριν, με αυτούς θα ασχοληθούμε
        μετά. Καταμετρητής αυτής της φάσης είναι μόνο ένας, ο
        ορισμένος ως αργηγός. Στη φάση 4 το άναμμα της λάμπας
        μετράει για 8 και ο αργηγός καταμετρά 8 επιπλέον
        παρουσίες για κάθε φορά που βρίσκει αναμμένη τη λάμπα.
Φάση 5: Στη φάση 5 συμμετέχουν ο αρχηγός και όσοι έχουν καταμετρήσει
        4 ή παραπάνω παρουσίες στις προηγούμενες φάσεις, και δεν
        προλαβαν να ανάψουν τη λάμπα για να "παραδώσουν" αυτές
        τις παρουσίες σε άλλο καταμετρητή ή τον αρχηγό.
        Καταμετρητής αυτής της φάσης είναι μόνο ο αργηγός.
        Στη φάση 5 το άναμμα της λάμπας μετράει για 4 και ο αργηγός
        καταμετρά 4 επιπλέον παρουσίες
        για κάθε φορά που βρίσκει αναμμένη τη λάμπα.
Φάση 6: Στη φάση 6 συμμετέχουν ο αρχηγός και όσοι έχουν καταμετρήσει
        2 ή παραπάνω παρουσίες στις προηγούμενες φάσεις, και δεν
        πρόλαβαν να ανάψουν τη λάμπα για να "παραδώσουν" αυτές
        τις παρουσίες σε άλλο καταμετρητή ή τον αρχηγό.
        Καταμετρητής αυτής της φάσης είναι μόνο ο αργηγός.
        Στη φάση 6 το άναμμα της λάμπας μετράει για 2 και ο αργηγός
        καταμετρά 2 επιπλέον παρουσίες για κάθε φορά που βρίσκει
        αναμμένη τη λάμπα.
Φάση 7: Στη φάση 7 συμμετέχουν ο αρχηγός και όσοι έχουν παρουσίες
        στις προηγούμενες φάσεις, και δεν πρόλαβαν να ανάψουν τη
        λάμπα για να τις "παραδώσουν" σε άλλο καταμετρητή ή τον
        αρχηγό. Καταμετρητής αυτής της φάσης είναι μόνο ο αργηγός.
        Στη φάση 7 το άναμμα της λάμπας μετράει για 1 και ο αργηγός
        καταμετρά 1 επιπλέον παρουσίες για κάθε φορά που βρίσκει
        αναμμένη τη λάμπα.
Οποιαδήποτε στιγμή ο αργηγός καταμετρήσει 100 παρουσίες στο δωμάτιο
ανακοινώνει το γεγονός και εςλευθερώνονται όλοι.

Για να δουλέψει η στρατηγική πρέπει κάθε φάση να έχει προκαθορισμένη
διάρκεια.

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

Από προσομοιώσεις και με κατάλληλη διάρκεια για τις διάφορες φάσεις
φαίνεται οτι ο μέσος όρος ημερών μέχρι την αποφυλάκιση είναι κάτω
από 5.000 ημέρες.

Η παραπάνω περιγραφή δεν αντιμετωπίζει όλες τις λεπτομέρειες. Π.χ.
τι γίνεται αν κάποιος ανάψει τη λάμπα στο τέλος της φάσης 1 και αυτή
δεν καταμετρηθεί από κανένα μέσα στη φάση 1 αλλά μείνει αναμένη στην
αρχή της φάσης 2; Αυτές αφήνονται ως άσκηση για τον αναγνώστη ;-)

Μετά τη εύρεση της λύσης που περιγράφεται παραπάνω ως λύση 2 ο
George Papargiris έδειξε ενδιαφέρον για την ύπαρξη πιο γρήγορης
λύσης και μετά απο μερικά hints κατάφερε να βρεί και μια παραλλαγή
της λύσης που δίνεται παραπάνω ως λύση 3.

Σωστές απαντήσεις έδωσαν οι

Damianos Karakos * (τη λύση που δώθηκε παραπάνω ως 1η λύση)
George Papargiris * (τη λύση που δώθηκε παραπάνω ως 2η λύση
                          και μετά από υποδείξεις και τη λύση που
                          δώθηκε παραπάνω ως 3η λύση)
Yiannis Papagrigorakis * (παραλλαγή της λύσης που δώθηκε παραπάνω
                          ως 1η λύση)
trabukos (τη λύση που δώθηκε παραπάνω ως 2η λύση)
Panos (τη λύση που δώθηκε παραπάνω ως 2η λύση)

Οι έχοντες * δώσαν και ανάλυση για τον υπολογισμό του μέσου χρόνου
μέχρι την απελευθέρωση. Για το λόγο αυτό λαμβάνουν και τον υποσχεθέντα
έπαινο!

Αν ξέχασα κάποιον, παρακαλώ να με συγχωρέσει και να μου το θυμίσει
για να διορθώσω.

Φιλικά,

Βαγγέλης

_______________________________________________________________

      Quiz of the Day ... Ελληνική Λίστα με σπαζοκεφαλιές
             https://anekdota.duckdns.org

        ___ Η QotD βγαίνει σε Ελληνικά και Greeklish ___
_______________________________________________________________


Γραφτείτε και εσείς στην Ελληνική Λίστα με σπαζοκεφαλιές (QotD) και στείλτε τα κουίζ σας!!!

Επιστροφή στον κεντρικό κατάλογο αυτού του αρχείου