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

Σεπτεμβρίου 3, 2008

Πώς θα απελευθερωθούν;

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

Ένας διεθυντής φυλακής έχει 100 φυλακισμένους και θα παίξει μαζί τους το εξής παιχνίδι: Θα τους βάλει στη σειρά, τον ένα πίσω από τον άλλο, και θα φορέσει σε καθένα από ένα πράσινο, κόκκινο ή μπλέ καπέλο. Κατόπιν θα τους ρωτήσει έναν-έναν, αρχίζοντας από τον τελευταίο, τι χρώμα καπέλο φορούν. Όποιος βρίσκει τι χρώμα καπέλο φοράει θα απελευθερώνεται, αλλιώς όχι.

Δείξτε ότι οι φυλακισμένοι μπορούν να συνεννοηθούν και να απαντήσουν με τέτοιο τρόπο ώστε να απελευθερωθούν τουλάχιστον οι 99 από αυτούς.

Η συνεννόηση πρέπει να γίνει πριν μπουν στη γραμμή και τους φορέσει τα καπέλα. Μετά απαγορεύεται η επικοινωνία μεταξύ τους, πέρα από το ότι ακούν όλοι τι απάντηση δίνει ο κάθε άλλος στην ερώτηση «Τι χρώμα καπέλο φοράς;».

Διευκρινίζεται ότι ο τελευταίος της γραμμής (ο Νο 100), ο οποίος απαντάει πρώτος, βλέπει τα καπέλα όλων των άλλων, ο Νο 99 βλέπει τα καπέλα των Νο 98 έως Νο 1, κλπ. Ο Νο 1 (ο πρώτος στη γραμμή) δε βλέπει τίποτα (και απαντάει τελευταίος).

Το πρόβλημα αυτό το έμαθα από τον Παναγιώτη Παπάζογλου.

Advertisements

8 Σχόλια »

  1. Πρέπει να απαντάν απλά μονολεκτικά πχ. «πράσινο» ή μπορεί να πει και άλλες αληθείς προτάσεις.. (πχ. «Δεν φοράω κόκκινο, φοράω πράσινο» ?

    Μου αρέσει!

    Σχόλιο από woci — Σεπτεμβρίου 4, 2008 @ 1:48 μμ

  2. Μονολεκτικά.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Σεπτεμβρίου 4, 2008 @ 1:49 μμ

  3. Υπόδειξη:

    Κάντε το για δυο χρώματα πρώτα.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Σεπτεμβρίου 6, 2008 @ 1:11 μμ

  4. ego pistevo oti af bruna na exoun sinenenoh8ei apo prin 8a sinenoh8un o ka8enas na leei t xroma t kapelou p foraei o brostinos t etsi o 100 dn 8a apelef8ero8ei epd kanes dn 8a pei t xroma t alla 8a apelef8ero8oun oi alloi 99

    Μου αρέσει!

    Σχόλιο από tsitsos — Σεπτεμβρίου 14, 2008 @ 5:00 πμ

  5. tsitsos:

    Για να απελευθερωθεί κάποιος πρέπει να πει το χρώμα που φοράει αυτός. Με τη δικιά σου μέθοδο αν φοράνε, π.χ,. κόκκινο και μπλέ εναλλάξ, δε θα απελευθερωθεί κανείς.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Σεπτεμβρίου 14, 2008 @ 8:32 πμ

  6. Υπόδειξη:

    Μετονομάστε τα χρώματα από κόκκινο, πράσινο, μπλέ σε 0, 1, 2. (Αν προσπαθείτε με δύο χρώματα τότε μετονομάστε τα σε 0,1..)

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Σεπτεμβρίου 16, 2008 @ 6:20 μμ

  7. Ας πούμε ότι έχουμε (μπλε,κόκκινο,πράσινο)=(0,1,2).
    Βασικά, ο τελευταίος φωνάζει το άθροισμα των καπέλων των 99 προηγούμενων, π.χ. 56, modulo 3 (στην original περίπτωση). Έτσι, ο 99ος, που φοράει έστω κόκκινο καπέλο, ξέρει το άθροισμα των προηγούμενων που βλέπει ότι είναι 55 και ότι ο 100ος φώναξε 56, άρα φονάζει κόκκινο. Ο 98ος, που φοράει έστω πράσινο καπέλο, ακούει 56 και κόκκινο (1) και μετράει το άθροισμα των μπροστινων του 53, άρα φοράει 56 – 1 – 53 = 2, δλδ. πράσινο. Έτσι όλοι σώζονται εκτός από τον 100.

    Μου αρέσει!

    Σχόλιο από Βαγγέλης — Σεπτεμβρίου 18, 2008 @ 2:33 πμ

  8. Σωστά, αυτή είναι η μέθοδος. Να διευκρινίσω ότι δε φωνάζει κανείς 55 ή 56 αλλά 55 mod 3 = 1 ή 56 mod 3 = 2. Μόνο αυτό του επιτρέπεται να πει αλλά αυτό αρκεί.

    Μια παρατήρηση ακόμη. Αυτό που ουσιαστικά χρησιμοποιείται εδώ είναι η δομή του συνόλου {0,1,2} ως προσθετική ομάδα.

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

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Σεπτεμβρίου 18, 2008 @ 7:58 πμ


RSS feed for comments on this post. TrackBack URI

Σχολιάστε

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

Λογότυπο WordPress.com

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

Φωτογραφία Twitter

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

Φωτογραφία Facebook

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

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

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

Σύνδεση με %s

Δημιουργήστε ένα δωρεάν ιστότοπο ή ιστολόγιο στο WordPress.com.

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