From: Vaggelis Kapoulas (kapoulas(@)cti.gr)
Date: Τρι 17 Σεπ 2002 - 10:46:08 EEST

• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
• Mail actions: [ respond to this message ] [ mail a new topic ]

Γει και χαρά,

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

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 επιπλέον παρουσίες για κάθε φορά που βρίσκει 
        αναμμένη τη λάμπα.

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

Η λύση αυτή βασίζεται (κατά κάποιο τρόπο) στην ιδέα της παράλληλης άθροισης 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 ___
_______________________________________________________________

• Next message: Yiannis Papagrigorakis: "ύση του CD-quiz"
• Previous message: Vaggelis Kapoulas: "Κυρτό στερεό και δαχτυλίδι"
• In reply to: Vaggelis Kapoulas: "100φυλακισμένοι και1λάμπα"
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
• Mail actions: [ respond to this message ] [ mail a new topic ]