Math Is Fun Forum

  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2014-08-12 19:00:59

anna_gg
Member
Registered: 2012-01-10
Posts: 232

Variation of mastermind game

We are playing 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 minimum number of tries, to get at least 2 black pegs?
Duplicates are allowed.

Offline

#2 2014-08-12 19:55:53

Olinguito
Member
Registered: 2014-08-12
Posts: 649

Re: Variation of mastermind game

Well, just from the way you phrase the question, the answer is 1. You might strike it lucky on your first move.

But I think you mean what is the minimum number of moves needed to be guaranteed at least two black pegs, assuming a worst-case scenario. Since repetition of colours are allowed there are 3³ = 27 permutations altogether. To get exactly two black pegs, the wrong position can be any of the 2 wrong colours, and there are 3 positions for the wrong colour to be, so there are 3 × 2 = 6 such permutations. And there is only 1 permutation for three black pegs (the winning sequence). Hence there are 27 − 6 − 1 = 20 permutations giving at most one black peg.

Therefore the answer to your question (assuming you don’t duplicate any of your moves) is 21. In the worst-case scenario you would try all the 20 permutations giving fewer than two black pegs first before you get warmer.


Bassaricyon neblina

Offline

#3 2014-08-13 19:51:40

anna_gg
Member
Registered: 2012-01-10
Posts: 232

Re: Variation of mastermind game

Thanks Olinguito! So my understanding is that in the end, you do not subtract the winning sequence, right? It is just 27-6.

Can you please explain "Hence there are 27 − 6 − 1 = 20 permutations giving at most one black peg"?

Offline

#4 2014-08-13 20:26:06

Olinguito
Member
Registered: 2014-08-12
Posts: 649

Re: Variation of mastermind game

anna_gg wrote:

Can you please explain "Hence there are 27 − 6 − 1 = 20 permutations giving at most one black peg"?

There are 6+1 permutations that earn at least two black pegs in the game so the number of those that give you at most one black peg is 27−(6+1).


Bassaricyon neblina

Offline

#5 2014-08-14 01:02:23

anna_gg
Member
Registered: 2012-01-10
Posts: 232

Re: Variation of mastermind game

Well, now that I reconsider the problem:
I agree that there are 27 permutations altogether. To be more specific, if we represent the 3 different colors with a, b and c, we would have:
aaa
aab
aac
aba
abb
abc
aca
acb
acc
baa
bab
bac
bba
bbb
bbc
bca
bcb
bcc
caa
cab
cac
cba
cbb
cbc
cca
ccb
ccc

As we can see, any combinations of 2 of the letters (out of 3), are repeated 3 times. For example, we have 3 x ?aa ?ab and ?ac, also 3 x b?a etc. Therefore with 9 tries at maximum, we can have a guaranteed win (2 colors in the correct place, thus 2 black pegs).

Offline

#6 2014-08-14 02:56:30

Olinguito
Member
Registered: 2014-08-12
Posts: 649

Re: Variation of mastermind game

Ah, I think I get the hang of the game. smile

Make your first move. If you have two or more black pegs, we are done (1 step). Otherwise you have either 0 or 1 black peg.

Case 1: 0 black pegs.
Try again, using a different colour for each position.
… (i) If you get 0 black pegs again, you know the correct combination (it’s the one where each position has the colour you haven’t tried for it) – and you can play it on your third move. In this case we achieve two or more black pegs in 3 steps.
…(ii) If you get 2 black pegs, we are done (2 steps).
…(iii) If you get 1 black peg, leave two colours and change one.
… … (a) If this gives you 0 black pegs, the colour you’ve changed was right before. In this case repeat step 1(i) and we are done in 4 steps.
… … (b) If this gives you 2 black pegs we are done (3 steps).
… … (c) If this gives you 1 black peg, the colour you’ve changed is still wrong – AND was wrong before. In this case you know the right colour for that position so you can put the right colour in that position for the rest of your movves. The black peg is for one of the other two positions. Change one of them. If the one you change is not the black-peg one, we are done (4 steps). Otherwise restore this colour and we are done (5 steps).

Case 2: 1 black peg.
Leave two colours and change one.
… (i) If you get 2 black pegs, we are done (2 steps).
… (ii) If you get 0 black pegs, the colour you’ve changed was right before. Restore it and change one of the other two.
… … (a) If this gives you 2 black pegs we are done (3 steps).
… … (b) If this gives you 1 black peg the colour you’ve changed is still wrong – AND was wrong before. So you know the correct colour for that position and we are done in 4 steps.
… … (c) You can’t get 0 black pegs because at this stage you already definitely the colour of one position.
… (iii) If you still get 1 black peg, the colour you’ve changed is still wrong – AND was wrong before. In this case you know the right colour for that position so you can put the right colour in that position for the rest of your moves.  The black peg is for one of the other two positions. Change one of them. If the one you change is not the black-peg one, we are done (3 steps). Otherwise restore this colour and we are done (4 steps).

So the most number of steps you need to take is actually 5 (Case 1(iii)(c)) if you reason correctly.


Bassaricyon neblina

Offline

Board footer

Powered by FluxBB