Author |
Topic: Master_mind (Read 847 times) |
|
Altamira_64
Junior Member
Posts: 116
|
 |
Master_mind
« on: Aug 14th, 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: 2873
|
|
Re: Master_mind
« Reply #1 on: Aug 14th, 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 14th, 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 14th, 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 14th, 2014, 10:23am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: Master_mind
« Reply #4 on: Aug 15th, 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 |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print