Mastermind: Win in two

Question

Bob was very lucky in his last game of Mastermind. Alice was the codemaker; Bob was the codebreaker. They played with six colors and a length four code.

Bob's first guess wasn't an immediate win. But after Alice scored the first guess, Bob was confident. "Then it must be this!" he said of his second guess. That second guess was the exact code, for the win.

Neither player cheated, there is no trick wording intended in this question, etc. Bob's reasoning was correct, that after the first guess and its score he knew the exact code for certain.

Your task: Based on this information, describe the possibilities for the code, the first guess, and the score for that guess!

Answer 1

This is an attempt to prove that there is only one possible setup, namely the one that Beastly Gerbil describes in their answer.

First, a couple of observations:

We must have guessed all colors on the first try, i.e. we got four (white or black) pegs as our first score. This must be true, otherwise we would have to guess a color on the second try. That is a contradiction to Bob's confidence.

We used between two and four colors on the first try. If we used only one color, we would have solved the code, based on the first observation. Since the code is of length four, we can use at most four colors.

The order of the colors does not matter, neither does the order of the scoring pegs.

The possible scores of the first try are WWWW, BWWW and BBWW. BBBW is not possible, it is an invalid state. BBBB would mean that we solved the code already.

That leaves us with

twelve different configurations (there are two possible ways to use two colors). That's few enough to check each for possible solutions of the code. If there's only one, the configuration is a solution to the puzzle.

Two colors AABB:

score WWWW: all colors are in the wrong position. The only way to solve this is BBAA. This configuration is a solution of the puzzle, and identical to the one that Beastly Gerbil found.

score BWWW: this is an invalid configuration. No matter which color we lock in place, we can not switch the other three colors around without one ending up in the same spot as before, which is a contradiction to the initial score of only one color being in the right spot.

score BBWW: BABA and ABAB are possible solutions.

Two colors AAAB (thanks @Joel Rondeau)

score WWWW: this is an invalid configuration. There is no way to switch all the colors without two of the As landing on a spot that was previously colored A. This is a contradiction to the initial score.

score BWWW: this is an invalid configuration. There is no way to lock one color and switch the remaining three without at least one of the As landing on a spot that was previously colored A. This is a contradiction to the initial score.

score BBWW: AABA and ABAA are possible solutions.

Three colors ABCC:

score WWWW: CCAB and CCBA are possible solutions.

score BWWW: CABC and BCAC are possible solutions.

score BBWW: CBCA and ACBC are possible solutions.

Four colors ABCD:

score WWWW: DCBA and BADC are possible solutions.

score BWWW: ACDB and CBDA are possible solutions.

score BBWW: ABDC and BACD are possible solutions.

So as a result

there is only one possible configuration. Two colors, AABB, and four white pegs as first score.

Answer 2

The code is of the format

XXOO, XOXO or XOOX - any combination of 2x2 colours.

For this answer we will use XXOO

Bob first guessed

OOXX

To which Alice responded with

4 white pegs, indicating 4 right colours all in the wrong position

So Bob knows for certain

That the correct code has to be the inverse of his first guess and gets it correct on his second go!

See @Christoph’s answer for proof this is the only solution!

Answer 3

A self-answer, just for comparison. Congrats to @Christoph and @BeastlyGerbil!

As Beastly Girbil started out,

If the score of the first guess had fewer than four White and Black total, then even if Bob could deduce which position(s) correspond to no scoring, a position which scored neither White nor Black could be any color at all except the one guessed there, so Bob couldn't deduce the correct color there. So scoring must have all four pegs, White or Black.

My next steps were slightly different:

Consider all the possible scores with four pegs total. Score BBBB is ruled out since Bob's first guess was not an immediate win. Score BBBW is never possible.

Suppose the score was BBWW. Alice's code is related to Bob's first guess by swapping two of the positions, which must be different colors. If the actual positions to be swapped are $W_1$ and $W_2$, and one of the black pegs was position $B_1$, then Bob can only rule out swapping the colors at $W_1$ and $B_1$ if positions $W_1$ and $B_1$ in his first guess are the same color. Similarly, Bob can only rule out swapping the colors at $W_2$ and $B_1$ if those two positions in his first guess are the same color. But then $W_1, B_1, W_2$ all have the same color, which contradicts the conclusion the swapped positions $W_1$ and $W_2$ have different colors. The score couldn't have been BBWW.

Suppose the score was BWWW. The three positions scored white must have three different colors: if two positions in the true code are the same color, then by the pigeonhole principle, any permutation puts at least one peg of that color in a position matching the code, so the score would not have three Whites. Even if Bob can deduce which position scored Black and which three scored White, there are two possible ways to permute three different colors with none of them in the original position: 123 to either 231 or 312. Bob could not be certain which of these was correct. The score was not BWWW.

The only remaining possibility is that the score of the first guess was WWWW.

And finishing up,

If any color appears three or more times in the code and guess, then by the pigeonhole principle at least two of the positions for that color match between the code and guess, and those would be two Black scores. So no color appears more than twice.

If the code and first guess contain four different colors, there are far too many possibilities for permutations which leave no peg in the same spot for Bob to know any one permutation is correct. (9 such permutations, I believe. But it's enough to say 1234 to 2341 and 1234 to 2143 are possibilites.) The code can't have four different colors.

If the code and first guess contain three different colors, one of those colors appears twice. Bob can deduce that repeated color appears in the two positions where he didn't guess it, but Bob can't know how to place the other two colors in the two positions where the guess had the repeated color. The code can't have three different colors.

So the code and the first guess have exactly two different colors, each appearing in two positions. Bob can find the code by changing the color in each position to the other color, and he is certain that's correct.