Faulty Combination Lock Puzzle – Minimum Number of Tries to Guarantee Opening It

Faulty Combination Lock – Πόσες δοκιμές χρειάζονται;

Έχουμε ένα λουκέτο συνδυασμού με τρεις δίσκους, και κάθε δίσκος έχει τους αριθμούς 1 έως 8. Το λουκέτο όμως είναι ελαττωματικό: αρκεί να είναι σωστοί οποιοιδήποτε δύο από τους τρεις αριθμούς για να ανοίξει.

Ερώτηση: Ποιος είναι ο ελάχιστος αριθμός τριψήφιων συνδυασμών που πρέπει να δοκιμάσουμε, ώστε να είμαστε σίγουροι ότι θα ανοίξει το λουκέτο;

➤ Λύση (πάτησε για εμφάνιση)

1. Πόσο «καλύπτει» ένας μόνο συνδυασμός;

Ένας δοκιμασμένος συνδυασμός, π.χ. (3,5,7), ανοίγει το λουκέτο αν:

• η πραγματική ρύθμιση είναι ακριβώς (3,5,7), ή
• συμφωνούν οι δύο πρώτοι (3,5,•), ή
• συμφωνούν η 1η και η 3η θέση (3,•,7), ή
• συμφωνούν η 2η και η 3η θέση (•,5,7).

Για κάθε ζεύγος θέσεων υπάρχουν 8 επιλογές για τον τρίτο αριθμό. Άρα ο κάθε συνδυασμός «καλύπτει»:

\(1 + 3\cdot(8-1) = 22\) διαφορετικές πραγματικές ρυθμίσεις.

Συνολικά υπάρχουν \(8^3 = 512\) δυνατοί κωδικοί. Αν δεν υπήρχαν επικαλύψεις, θα χρειαζόμασταν τουλάχιστον \(\lceil 512/22\rceil = 24\) δοκιμές. Άρα η απάντηση είναι τουλάχιστον 24.

2. Έξυπνη κατασκευή με 32 συνδυασμούς

Χωρίζουμε τους αριθμούς σε δύο ομάδες:

• Ομάδα Α: 1, 2, 3, 4
• Ομάδα Β: 5, 6, 7, 8

Πρώτα δουλεύουμε μόνο με την Ομάδα Α. Μπορούμε να φτιάξουμε 16 τριάδες από τους αριθμούς 1–4, με την ιδιότητα ότι κάθε ζεύγος θέσεων (π.χ. οι δύο πρώτοι αριθμοί) εμφανίζεται σε μία και μόνο μία τριάδα. Ένας κομψός τρόπος είναι να πάρουμε όλες τις τριάδες (a,b,c) με

\((a+b+c) \equiv 0 \pmod 4\), αν αντιστοιχίσουμε 1→0, 2→1, 3→2, 4→3.

Αυτές οι 16 τριάδες έχουν την εξής κρίσιμη ιδιότητα: αν ξέρουμε δύο θέσεις, η τρίτη είναι μοναδικά καθορισμένη και περιλαμβάνεται σε μία από τις 16 δοκιμές μας.

Κάνουμε ακριβώς το ίδιο για την Ομάδα Β (5–8), φτιάχνοντας άλλες 16 τριάδες με τον ίδιο κανόνα (mod 4, αλλά μετατοπισμένο). Έτσι έχουμε συνολικά:

16 + 16 = 32 συνδυασμούς.

3. Γιατί καλύπτουμε κάθε δυνατό κωδικό;

Πάρε οποιονδήποτε πραγματικό κωδικό του λουκέτου, π.χ. (2,7,8). Τουλάχιστον δύο από τα τρία ψηφία ανήκουν στην ίδια ομάδα: ή και τα δύο ≤4 ή και τα δύο ≥5. Στο παράδειγμα (2,7,8), τα 7 και 8 είναι και τα δύο στην Ομάδα Β.

Στην αντίστοιχη ομάδα (Α ή Β) οι τριάδες μας έχουν την ιδιότητα: κάθε ζεύγος θέσεων εμφανίζεται σε κάποια τριάδα. Άρα υπάρχει δοκιμή όπου αυτές οι δύο θέσεις είναι σωστές, κι ας είναι η τρίτη λάθος. Επειδή το λουκέτο ανοίγει μόλις δύο θέσεις είναι σωστές, ο κωδικός αυτός θα ανοίξει με μία από τις 32 δοκιμές μας.

4. Μπορούμε να κάνουμε λιγότερες από 32;

Από το μέτρημα με τις «μπάλες ακτίνας 1» (22 κωδικοί ανά δοκιμή) ξέρουμε ότι χρειαζόμαστε τουλάχιστον 24 δοκιμές. Με πιο προχωρημένα επιχειρήματα έχει αποδειχθεί ότι δεν γίνεται να καλύψουμε όλους τους κωδικούς με λιγότερες από 32 δοκιμές.

Τελικό συμπέρασμα: Μπορούμε να είμαστε σίγουροι ότι θα ανοίξει το λουκέτο με 32 συνδυασμούς, και αυτός ο αριθμός είναι βέλτιστος.

Faulty Combination Lock – How Many Tries Do You Need?

We have a combination lock with three dials, each dial showing the digits 1 through 8. The lock is faulty: it will open as soon as any two of the three digits are correct.

Question: What is the minimum number of three-digit combinations you must try to be certain of opening the lock?

➤ Solution (click to reveal)

1. How much does a single guess cover?

Take a guess such as (3,5,7). It opens the lock if:

• the true code is exactly (3,5,7), or
• the first two digits match: (3,5,•), or
• the first and third match: (3,•,7), or
• the last two match: (•,5,7).

For each pair of positions there are 8 choices for the remaining digit. So one guess covers

\(1 + 3\cdot(8-1) = 22\) possible true configurations.

There are in total \(8^3 = 512\) configurations. If there were no overlaps, we would need at least \(\lceil 512/22\rceil = 24\) guesses. Thus the answer is at least 24.

2. A clever construction with 32 guesses

Split the digits into two groups:

• Group A: 1, 2, 3, 4
• Group B: 5, 6, 7, 8

First work only with Group A. We can construct 16 triples using the digits 1–4 with the property that any pair of positions uniquely determines the third digit. One elegant way is to take all triples (a,b,c) such that

\((a+b+c) \equiv 0 \pmod 4\),

after mapping 1→0, 2→1, 3→2, 4→3. This set of 16 triples has the key property: for any choice of two coordinates, there is exactly one triple containing them.

We do the same with Group B (5–8), obtaining another 16 triples by the same mod 4 rule, shifted up by 4. Altogether we have

16 + 16 = 32 guesses.

3. Why does this cover every possible code?

Take any true code, say (2,7,8). At least two of its digits lie in the same group: either both ≤4 or both ≥5. In our example, 7 and 8 are both in Group B.

In the corresponding group (A or B), our 16 triples have the property that every pair of positions occurs in some triple. So there is a guess whose two matching coordinates are exactly those two digits, and the third digit may be wrong. Since the lock opens whenever any two positions are correct, that guess will open the lock.

4. Can we do better than 32?

The counting argument with “radius-1 balls” shows we need at least 24 guesses. Using deeper combinatorial arguments, one can prove that no set of guesses smaller than 32 can cover all 512 configurations.

Final result: We can guarantee opening the lock with 32 combinations, and this number is optimal.