wu :: forums « wu :: forums - Master_mind » Welcome, Guest. Please Login or Register. Nov 28th, 2023, 6:18pm RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    medium (Moderators: towr, Eigenray, Icarus, SMQ, william wu, ThudnBlunder, Grimbal)    Master_mind « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: Master_mind  (Read 844 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: 2865
 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: 2865
 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
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy => medium   - hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »