wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Master_mind
        
(Message started by: Altamira_64 on Aug 14^th, 2014, 1:09am)

Title: Master_mind
Post by Altamira_64 on Aug 14^th, 2014, 1:09am

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.

Title: Re: Master_mind
Post by rmsgrey on Aug 14^th, 2014, 7:13am

I can do it in [hide]4[/hide] turns:

[hideb]
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

[/hideb]

Title: Re: Master_mind
Post by Altamira_64 on Aug 14^th, 2014, 9:45am

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?

Title: Re: Master_mind
Post by towr on Aug 14^th, 2014, 10:10am

You do it as rmsgrey said

[hide]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.[/hide]

Title: Re: Master_mind
Post by rmsgrey on Aug 15^th, 2014, 4:00am

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 [hide]4[/hide]
Proof:
[hideb]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.
[/hideb]

As a variation, if you require all your guesses to be made before any get marked, I can do it in [hide]5[/hide]:

[hideb]
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.
[/hideb]