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

Ιουνίου 11, 2015

Ληστές επτά, με κάμποσα λεφτά

Filed under: Λυμένα Προβλήματα — Mihalis Kolountzakis @ 9:57 μμ

Μια ομάδα 7 ληστών μόλις διέπραξε μια πολύ επιτυχημένη ληστεία τράπεζας. Τα χρήματα που σήκωσαν τα έχουν βάλει σε ένα χρηματοκιβώτιο στο καταφύγιό τους. Πρέπει όμως να διαφυλάξουν αυτά τα χρήματα πρώτ’ απ’ όλα από τους ίδιους τους τους εαυτούς.

padlocks

Τι θα γίνει π.χ. αν σηκωθεί ένας από αυτούς τα πάρει και φύγει; Αυτό φυσικά δεν είναι αποδεκτό στην ομάδα. Ή αν δύο από αυτούς συμφωνήσουν μεταξύ τους και τα πάρουν και φύγουν; Ούτε κι αυτό είναι αποδεκτό.

Όμως πρόκειται για μια ομάδα κλεφτών μεγαλωμένη από τους γονείς τους με πίστη στα δημοκρατικά ιδεώδη. Αν λοιπόν κάποιοι 4 από αυτούς αποφασίσουν να τα πάρουν αυτό γίνεται αποδεκτό γιατί οι 4 είναι πλειοψηφία στους 7. Όχι όμως 3 ή λιγότεροι.

Πώς θα το υλοποιήσουν αυτό; Το χρηματοκιβώτιο έχει απ’ έξω ένα μεγάλο σίδερο πάνω στο οποίο μπορούν να μπουν πολλά λουκέτα και όλα αυτά πρέπει να ξεκλειδωθούν για να ανοίξει. Για κάθε λουκέτο μπορούμε να έχουμε όσα αντικλείδια χρειαζόμαστε.

Πρέπει λοιπόν να δώσουμε σε κάθε κλέφτη ένα σετ από κλειδιά με τέτοιο τρόπο ώστε:

  1. Οποιοιδήποτε 4 κλέφτες να έχουν μεταξύ τους όλα τα κλειδιά που απαιτούνται για να ανοίξει το χρηματοκιβώτιο.
  2. Για οποιουσδήποτε 3 κλέφτες αυτό δε συμβαίνει.

Πώς μπορεί  να γίνει αυτό; Πόσα λουκέτα συνολικά χρειάζονται και ποια κλειδιά θα πάρει κάθε κλέφτης;

Advertisements

10 Σχόλια »

  1. Ας υποθέσουμε ότι 3 κλέφτες προσπαθούν να ανοίξουν το χρηματοκιβώτιο (κάτι που από την υπόθεση είναι αδύνατο)
    επομένως πρέπει να υπάρχει ένα λουκέτο που αυτοί οι 3 δεν μπορούν να ανοίξουν. Γι αυτό το λουκέτο πρέπει να έχει κλειδί
    ένας από τους εναπομείναντες 4 κλέφτες.Επομένως για κάθε «ομάδα» από τρεις κλέφτες πρέπει να υπάρχει ένα λουκέτο που δεν μπορούν να ανοίξουν.
    Υπάρχουν (7 ανά 3)=35 «ομάδες τριών κλεφτών» οπότε χρειαζόμαστε 35 λουκέτα.

    Μου αρέσει!

    Σχόλιο από Δημήτρης Παπαδάκης — Ιουνίου 11, 2015 @ 11:16 μμ

  2. Καλή αρχή αλλά κάποια ερωτήματα:

    1. Γιατί αυτά τα 35 κλειδιά (ένα για κάθε τρεις από τους επτά) πρέπει να είναι όλα διαφορετικά μεταξύ τους;

    2. Γιατί αρκούν τα 35 κλειδιά; Αν αρκούν πώς πρέπει να μοιραστούν;

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Ιουνίου 11, 2015 @ 11:21 μμ

  3. Για το ερώτημα 1:
    Ας συμβολίσουμε τους κλέφτες Κ1,Κ2,Κ3,Κ4,Κ5,Κ6,Κ7
    ΥΠΟΘΕΣΗ: Δεν είναι όλα τα 35 κλειδιά διαφορετικά μεταξύ τους.
    Συνεπώς δύο διαφορετικές ομάδες τριών κλεφτών χρειάζονται το ίδιο κλειδί για να ανοίξουν το χρηματοκιβώτιο.
    Επομένως ισχύει:
    Η ομάδα «Κ1, Κ2, Κ3» χρειάζεται ακόμα το κλειδί Κ για να ανοίξουν το χρηματοκιβώτιο.
    Η ομάδα «Κ1, Κ2, Κ4» χρειάζεται ακόμα το κλειδί Κ για να ανοίξουν το χρηματοκιβώτιο.
    Όμως η ομάδα «Κ1, Κ2, Κ3, Κ4», που αποτελείται από 4 κλέφτες πάλι δεν μπορεί να ανοίξει το χρηματοκιβώτιο καθώς τους λείπει το κλειδί Κ.
    ΑΤΟΠΟ!!!, γιατί οποιαδήποτε ομάδα από 4 κλέφτες θα έπρεπε να μπορεί να ανοίξει το χρηματοκιβώτιο.
    Άρα η υπόθεση είναι λανθασμένη επομένως όλα τα κλειδιά είναι διαφορετικά μεταξύ τους.

    Μου αρέσει!

    Σχόλιο από Δημήτρης Παπαδάκης — Ιουνίου 11, 2015 @ 11:46 μμ

  4. Ωραία, και γιατί φτάνουν τα 35 κλειδιά, και πώς πρέπει να μοιραστούν;

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Ιουνίου 11, 2015 @ 11:47 μμ

  5. Μιχάλη, Nομίζω πώς άλλο λουκέτο ,άλλο κλειδί. Ο κος Παπαδάκης στο σχόλιό του με το οποίο συμφωνώ μιλάει για c(7,3)=35 λουκέτα. Κάθε υποσύνολο των 3 κλεφτών πρέπει (για να είναι η λύση μας η ελάχιστη δυνατή) να μην μπορεί να ανοίξει ένα και μόνο λουκέτο από τα υπόλοιπα.
    Τώρα, ο κλέφτης έστω Χ πρέπει να έχει το 1 κλειδί που λείπει διά ΚΑΘΕ γκρουπ των τριών (από τα 35) στο οποίο δεν ανήκει ο ίδιος. Ήτοι c(6,3)=20 κλειδιά.
    Οι δυνατοί Χ όμως είναι και οι 7. Άρα 7*20=140 κλειδιά κατ’ελάχιστον . (και 35 λουκέτα)
    Η διανομή των κλειδιών -όπως προκύπτει βέβαια από τα παραπάνω- θα γίνει ως εξής: Σε κάθε μία από τις 35 κλειδαριές αντιστοιχίζουμε μία διακριτή τριάδα από τις 35. Π.χ στην πρώτη βάζουμε ετικέτα «1-2-3» στην επόμενη «1-2-4» κ.ο.κ. (οι 7 κλεφτες είναι προφνώς οι 1,2,3,…,7).
    Δίνοντας σε κάθε κλέφτη το κλειδί από κάθε λουκέτο που ΔΕΝ έχει πάνω του τον αριθμό που αντιστοιχεί στον κλέφτη, τελειώσαμε.

    Μου αρέσει!

    Σχόλιο από George Rizopulos — Ιουνίου 12, 2015 @ 12:08 πμ

  6. Γιώργο, η διακριτή τριάδα σε κάθε μία από τις κλειδαριές τί μας λέει;

    Μου αρέσει!

    Σχόλιο από Κωνσταντίνος Κουρουζίδης — Ιουνίου 12, 2015 @ 12:20 πμ

  7. Κάθε ομάδα από τρεις κλέφτες μπορεί να ανοίξει το πολύ 34 λουκέτα γιατί πάντα της λείπει ένα κλειδί. Για παράδειγμα η ομάδα «Κ1 Κ2 Κ3» μπορεί να ανοίξει 34 λουκέτα. Οπότε καθένας από τους υπόλοιπους 4 κλέφτες Κ4,Κ5,Κ6,Κ7 πρέπει να έχει μαζί του το κλειδί για το 35ο λουκέτο.
    Άρα για κάθε 3άδα κλεφτών θέλουμε 4 κλειδιά για ένα συγκεκριμένο λουκέτο.
    Επομένως χρειαζόμαστε (7 ανά 3)*4=140 κλειδιά για όλους τους κλέφτες και ο καθένας θα πάρει 140/7=20 κλειδιά.

    Μου αρέσει!

    Σχόλιο από Δημήτρης Παπαδάκης — Ιουνίου 12, 2015 @ 12:23 πμ

  8. 5, 7. Φυσικά με κλειδιά εννοούσα «διαφορετικά κλειδιά» που είναι το ίδιο με τα διαφορετικά λουκέτα.

    Ανακεφαλαιώνω λοιπόν τη λύση:

    Υπάρχουν 35 τριάδες κλεφτων. Για κάθε τριάδα αγοράζουμε ένα λουκέτο και 4 αντίγραφα του κλειδιού και τα δίνουμε στους υπόλοιπους 4. Άρα αυτή η κάθε τριάδα έχει τουλάχιστον ένα λουκέτο που δε μπορεί να ανοίξει.

    Ας εξετάσουμε τώρα μια 4άδα κλεφτών. Δεν της λείπει κανένα από τα 35 κλειδιά γιατί κάθε κλειδί δόθηκε σε 4 άτομα άρα δε μπορεί να το έχουν μόνο οι υπόλοιποι 3. Άρα κάθε 4άδα ανοίγει.

    Ωραία.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Ιουνίου 12, 2015 @ 12:27 πμ

  9. Μιχάλη, δεν ήξερα ότι οι απαντήσεις είναι ανοικτές. Anyway, μια που έγραψα τη διαδικασία που ακολούθησα εγώ την κάνω copy-paste:

    Άτομα Α={α1,…,α7}. Οι συνδυασμοί των 7 ληστών ανά 4 = 35 (άρα έχουμε 35 διαφορετικές τετράδες ληστών) που κάθε μία από αυτές πρέπει να μπορεί να ανοίξει τα λουκέτα, άρα η ένωση των κλειδιών που έχει πρέπει να είναι το σύνολο Λ.
    Υπόθεση: Λουκέτα Λ = {λ1, … , λ7}.
    Κάθε κλειδί (ενός λουκέτου) δεν δίνεται σε 7-4=3 άτομα, δίνεται λοιπόν σε 4 άτομα.
    Γιατί 4 άτομα τα καταφέρουν; Γιατί κάθε κλειδί δεν έχει δοθεί σε 3 άτομα, οπότε μια τετράδα ατόμων σίγουρα έχει ένα άτομο που το έχει.
    Γιατί 3 άτομα δεν τα καταφέρνουν; Γιατί δεν μπορούν να ανοίξουν εκείνο το λουκέτο που δεν έχει δοθεί σε αυτή την συγκεκριμένη τριάδα. Άρα χρειάζεται για κάθε μία τριάδα να υπάρχει ένα κλειδί (που δεν έχει), άρα χρειαζόμαστε τελικά 35 κλειδιά (όχι 7).
    Νέα υπόθεση: Λουκέτα Λ = {λ1, … , λ35}.
    Επαλήθευση: Κάθε κλειδί (ενός από τα 35 λουκέτα) δεν δίνεται σε 7-4=3 άτομα, δίνεται λοιπόν σε 4 άτομα. Γιατί 4 άτομα τα καταφέρουν; Γιατί κάθε κλειδί δεν έχει δοθεί σε 3 άτομα, οπότε μια τετράδα ατόμων σίγουρα έχει ένα άτομο που το έχει. Γιατί 3 άτομα δεν τα καταφέρνουν; Διότι δεν μπορούν να ανοίξουν εκείνο το λουκέτο που δεν έχει δοθεί σε αυτή την συγκεκριμένη τριάδα και αυτό ισχύει για κάθε μία από τις 35 δυνατές τριάδες.

    Μου αρέσει!

    Σχόλιο από Yannis Tzitzikas — Ιουνίου 12, 2015 @ 2:13 πμ

  10. Έχω και εγώ με τη σειρά μου να προτείνω μια λύση στο πρόβλημα αυτό λίγο διαφορετική.

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

    Κατασκευαστικά τώρα θα υπολογίσω το πόσα είναι τα λουκέτα. Έστω Κν ο νιοστός κλέφτης.

    Ο Κ1 σκέπτεται λίγο πονηρά και πάει και βάζει στο κουτί 6 ανά 3 λουκέτα, με τέσσερα αντικλείδια το καθένα. Κρατά από κάθε λουκέτο 1 αντικλείδι και σε κάθε πιθανή τριάδα από τους Κ2 μέχρι Κ7 αντιστοιχίζει ένα λουκέτο και δίνει ένα κλειδί σε κάθε μέλος της τριάδας. Με αυτό τον τρόπο ανά τρεις οι κλέφτες από την ομάδα Κ2 μέχρι Κ6 δεν μπορούν να συμπληρώσουν όλα τα κλειδιά του Κ1. Όμως ο Κ1 μόνος του μπορεί να πάρει το θησαυρό.

    Έτσι ο Κ2 θεωρώντας τον εαυτό του ριγμένο προσθέτει 5 ανά 3 λουκέτα στο κουτί, με τέσσερα αντικλείδια το καθένα. Κρατά από κάθε λουκέτο 1 αντικλείδι και σε κάθε πιθανή τριάδα από τους Κ3 μέχρι Κ7 αντιστοιχίζει ένα λουκέτο και δίνει ένα κλειδί σε κάθε μέλος της τριάδας. Κάθε λοιπόν τριάδα από τους Κ3 μέχρι Κ7 δεν μπορούν να ανοίξουν το κουτί αφού τους λείπει κάποιο από τα κλειδιά που έχει ο Κ1. Ενώ κάθε πιθανή δυάδα αυτών μαζί με τον Κ1 δεν μπορούν να ανοίξουν το κουτί επειδή θα τους λείπει κάποιο κλειδί του Κ2. Έτσι ο Κ2 εξασφαλίζει πως δεν υπάρχει τριάδα που να ανοίγει το κουτί χωρίς να είναι και αυτός μέλος της.

    Βλέποντας αυτή την κατάσταση ο Κ3 θεωρεί τον εαυτό του ριγμένο, αφού αν συνασπιστούν ο Κ1 με τον Κ2 μπορούν να ανοίξουν το κουτί. Προσθέτει λοιπόν 4 ανά 3 λουκέτα στο κουτί, με τέσσερα αντικλείδια το καθένα. Κρατά από κάθε λουκέτο 1 αντικλείδι και σε κάθε πιθανή τριάδα από τους Κ4 μέχρι Κ7 αντιστοιχίζει ένα λουκέτο και δίνει ένα κλειδί σε κάθε μέλος της τριάδας. Όμοια λοιπόν ο Κ3 έχει εξασφαλίσει πως κάθε τριάδα που δεν τον περιέχει στερείται ενός κλειδιού.

    Τέλος ο Κ4 παρατηρώντας πως μόνο η τριάδα που περιέχει τους Κ1, Κ2, Κ3 ανοίγει το κουτί προσθέτει στο κουτί ένα λουκέτο, με τέσσερα αντικλείδια, κρατάει ένα κλειδί και δίνει από ένα κλειδί στους Κ5, Κ6, Κ7. Έτσι εξασφαλίζει πως καμία τριάδα κλεφτών δεν μπορεί να ανοίξει το κουτί.

    Τέλος λόγω της αρχής του Dirihlet κάθε τετράδα έχει όλα τα κλειδιά από μια τουλάχιστον φορά!

    Τα λουκέτα λοιπόν πρέπει να είναι σε πλήθος:
    6ανά3 + 5ανά3 + 4ανά3 + 3ανά3 = 20 + 10 + 4 + 1 = 35

    Μου αρέσει!

    Σχόλιο από Charidimos Kiosterakis — Ιουνίου 12, 2015 @ 2:22 πμ


RSS feed for comments on this post. TrackBack URI

Σχολιάστε

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

Λογότυπο WordPress.com

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

Φωτογραφία Twitter

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

Φωτογραφία Facebook

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

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

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

Σύνδεση με %s

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

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