Author 
Topic: Master_mind (Read 844 times) 

Altamira_64
Junior Member
Posts: 116


Master_mind
« on: Aug 14^{th}, 2014, 1:09am » 
Quote Modify

Let's play a mastermind game with 3 colors and 3 positions (holes). There is no white key peg (indicating the existence of a correct color code peg placed in the wrong position)  just black pegs, for each code peg from the guess that is correct in both color and position. What is the least number of tries, to have a guaranteed minimum of 2 black pegs? Duplicates are allowed.


IP Logged 



rmsgrey
Uberpuzzler
Gender:
Posts: 2865


Re: Master_mind
« Reply #1 on: Aug 14^{th}, 2014, 7:13am » 
Quote Modify

I can do it in 4 turns: hidden:  Using colours a, b, c: 1: aaa 2: bbb That establishes what colours the three solution pegs are (but not their order)  if you've only had 0 or 1 black pegs in total so far, the third line is ccc to finish; if you've had 2 or 3 black pegs at once, you're already done. The only other possibility is one of each colour: 3: bbc with 0 black pegs: 4: ccb with 1 black peg: 4: bba with 2 black pegs: done 


IP Logged 



Altamira_64
Junior Member
Posts: 116


Re: Master_mind
« Reply #2 on: Aug 14^{th}, 2014, 9:45am » 
Quote Modify

Yes, but what if you have one black peg after aaa (meaning you have exactly one a) and another black peg after bbb (meaning you also have exactly one b)? Then you know it's a, b and c but you don't know the order. How do you make it with another 2 guesses?


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: Master_mind
« Reply #3 on: Aug 14^{th}, 2014, 10:10am » 
Quote Modify

You do it as rmsgrey said Try bbc as 3rd guess If the c is correct, then one of the b's must be correct because all three colours are used. So if you don't have at least two black pegs, you know c is wrong. If you have one black peg, therefor one of the two b's must be correct, because the c cannot be correct by itself. So the third position must be a, therefor making the fourth guess bba gives two black pegs. If you have no black pegs, then the third one must have been b, because every colour should be there and it's not the first two. And since one of the other two has to be a or c, either aab or ccb as fourth guess would work.

« Last Edit: Aug 14^{th}, 2014, 10:23am by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



rmsgrey
Uberpuzzler
Gender:
Posts: 2865


Re: Master_mind
« Reply #4 on: Aug 15^{th}, 2014, 4:00am » 
Quote Modify

Further observations: Notation: Since the peg in each position is marked independently of the pegs in the other positions, any assignment of colours to symbols can vary from position to position  in particular, for each position you can use 'a' for the colour guessed in that position on your first move, 'b' for the second distinct colour you guess in that position, and 'c' for the remaining colour  so 'aaa' is any combination, 'bbb' is any other combination with no matches to 'aaa' and 'ccc' is the unique combination that doesn't match either. The fewest moves possible to guarantee getting at least 2 black pegs for the same move is 4 Proof: hidden:  For any given first move, there are 7 answer combinations that give 2 or 3 black pegs, 12 that give 1 and 8 that give 0. If your first move gives 1 black peg, your second move can then match your first in 0, 1, 2, or 3 places. To be guaranteed to be done in 3 moves or fewer, you need to account for at least 5 of the 12 possibilities remaining: 0 matches (bbb): accounts for 3 combinations (abb, bab, bba) 1 match (abb): accounts for 3 combinations (abb, acb, abc) 2 matches(aab): accounts for 4 combinations (abb, acb, bab, cab) 3 matches (aaa): accounts for 0 combinations. Since there must be at least 8 possibilities left to account for, and at most 7 can be accounted for by the third move, it must take at least 4 moves to account for every possible combination.  As a variation, if you require all your guesses to be made before any get marked, I can do it in 5: hidden:  1) aaa 2) bbb 3) acc 4) cac 5) cca If there are 2 or 3 of a or of b, then the first two moves will cover it; if there are 2 or 3 of c, then, obviously, the remaining moves cover it. The only other possibility is one of each  a,b,c in some order  but the last three moves also cover those  the a has to match in one of them, and when it does, so must one c. 


IP Logged 



