6
$\begingroup$

This a variation of the traditional game mastermind. There are 4 pegs and 6 colors of pegs in the code (repeats allowed). All rules are as usual, except for this one:

You are not given any hints (black and white pegs) after making a single guess. Instead, you must enter a series of $n$ guesses. After this, you are given all the hints to all the guesses. However, you must now enter your final guess.

What is the minimum value of $n$ for which you can guarantee your win? Also give the $n$ guesses and proof that it always works.

Twist (much harder)

You enter $n$ guesses and get the hints for them after the input. Then you enter $m$ guesses and get the hints after input. Now you make your final guess. Minimize $m+n$ so you can still guarantee a win.

$\endgroup$
  • $\begingroup$ Are the hints properly ordered to match with the guesses? $\endgroup$ – Ian MacDonald Jul 6 '15 at 11:08
  • $\begingroup$ @ghosts_in_the_code I think the solution is 6 regardless of how you divide them up. $\endgroup$ – Joe Z. Jul 6 '15 at 15:25
  • $\begingroup$ @IanMacDonald Yes, you are using the usual board. $\endgroup$ – ghosts_in_the_code Jul 6 '15 at 15:35
4
$\begingroup$

My guess is 6. At least with the following guesses you can know the solution

0001
0123
2414
4502
1453
0115

I used a computer program to get this. My approach was first to match every move with every solution and see how many different pin configurations there were and take the first move that has the maximum value for this. After that take that 'best' move and try again every move to every solution and see how many pin configurations there was for these 2 moves combined and pick the highest value again, and so on until I got $6^4 = 1296$ different pin configurations.

The resulting pin configurations for the above 6 moves can be seen at http://pastebin.com/hCGMdnxa where the first number is the amount of black pins and the second the amount of white pins. What you find is that every solution has a different pin configuration.

This is a greedy algorithm and not optimal but my guess is that it gives the right answer although I can't prove it.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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