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?
2 Answers
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.
-
$\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$– OrayApr 4 at 7:39
The standard strategy for Mastermind is:
- Make a list of all possible codes
- Make the first code your guess. This will give you 0-4 beeps
- Go through the list, and remove all options that, when compared to your guess, do not give the same number of beeps
- 1234 guess gets 1 beep
- 1243 compared to 1234 would give 2 beeps, so remove it
- 1342 gives 1 beep so it stays
- 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.