3
$\begingroup$

You are trying to open a safe. There are 4 locks and 4 keys (red, green, blue and yellow). When you insert the keys into the locks, the safe will make k beeps, where k is the number of keys that are in the correct lock. If all keys are in the correct locks then the safe will open. Otherwise you can make further attempts to open the safe. Can you come up with a strategy that minimizes the number of attempts to open the safe in the worst case?

$\endgroup$

2 Answers 2

2
$\begingroup$

This simplified version of Mastermind only considers the correct locations. Firstly we know that

there are 24 possibilities. P(4,4)

To simplify things,

let's refer to the keys as $(a,b,c,d)$ instead of colors, and place them into the locks.

there are 4 possibilities;

one is

one beep (Case 1), This implies that only one location is correct and the others are incorrect.

the other is

two beeps (Case 2) two locations are correct, two others are incorrect

and the other one is

0 beep (Case 3), none is correct.

and lastly of course

unlocking

It is not possible

to have three (3) beeps, as it would be illogical to have three correct locations and one incorrect location.

let's say we guessed $(a,b,c,d)$,

and if Case 1 happens;

there are 8 possibilities left (acdb, adbc...)

the second guess should be

one of the possible answers (let's say $(a,c,d,b)$ as second guess)

By choosing your guess

from the possible outcomes, you may encounter Case 1.1, Case 1.3, or successfully unlock the lock using the same logic as explained earlier. However, Case 1.2 is not a possible outcome.

If it is Case 1.1

there are 4 possibilities (adbc,bcad,dacb,cbda)

We need to make a new guess

that is not included in the first 8 possibilities, as otherwise, we would not receive any beeps. The new guess should begin with the letter "a" (or the first guess' color) but must not be among the options we discovered in Case 1. such as abdc, acbd, adcb.

this will result

Case 2 with two beeps or Case 3 with no beeps. and this will make the options into two only. Because out of 4 possibilities, 2 of them could be Case 2, the other two would be Case 3. So after that, the next guess will tell you if you find out the right order 100%. (3 guesses to find the right order, 4 times try at most to open the lock)

Let's come to Case 2

with 2 beeps.

There are

6 possibilities with this one (abdc, acbd, adcb, bacd, cbad, dbca). For the next step, we will guess not among the possibilities because it will result only one beep whatever guess you do

so we will consider

any non-possible option starting with $a$. (for this case $acdb$ or $adbc$)

this will result only two possible conditions:

Case 2 with 2 beeps or Case 3 with 0 beep. if it is Case 2, that means it starts with $a$ (3 possibilities) if it is Case 3, that means it does not start with $a$. (3 possibilities)

after this

We must make individual guesses, and in the worst-case scenario, we will determine the correct order in four attempts. We will successfully unlock the safe on the fifth attempt.

let's come to the Case 3 where

no beep for your $abcd$ guess

that means

9 possibilities (badc, bcda, ...)

Our next guess should be

sometime like $badc$, which implies that the first and second positions are switched, and the third and fourth positions are likely switched with each other. Note that, this could be another switch like b<->c and a<->d, that would not change the outcome in the amount of Cases.

if this happens,

there will be only two possible beeps, Case 2 and Case 3.

if it is Case 2

you can guess among the possible 4 outcomes, this will make the outcome Case 1 or Case 3. and it will be just another guess if you did not find the correct order to find the right order (in total 4 tries to figure out the correct order, 5 tries to open it)

and if it is Case 3

you will do the same as Case 2. that would be the same thing.

At the end, we can say that

in worst case, at most 4 tries to find the right order and 5 tries to open the safe.

$\endgroup$
2
  • $\begingroup$ Very nice! I believe that works. Can we do any better? $\endgroup$ Apr 4 at 7:30
  • $\begingroup$ @DmitryKamenetsky I do not think that is possible, I considered every possible conditions in my opinion, but anyone is free to try something better :) $\endgroup$
    – Oray
    Apr 4 at 7:39
-2
$\begingroup$

The standard strategy for Mastermind is:

  1. Make a list of all possible codes
  2. Make the first code your guess. This will give you 0-4 beeps
  3. Go through the list, and remove all options that, when compared to your guess, do not give the same number of beeps
    1. 1234 guess gets 1 beep
    2. 1243 compared to 1234 would give 2 beeps, so remove it
    3. 1342 gives 1 beep so it stays
  4. Go to step 2

This strategy gives 6 guesses in the worst case for this puzzle. This is actually the same as regular mastermind, which suggests to me there's probably a better solution.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.