Mastermind(english)

(February 2002)
Find here a short proof of a few results for static mastermind.
For generell informations first look to the very nice homepage of Cut The Knot !
Some more detail informations are on my german page for mastermind !

The first goal of this page is, to compute the complexity of the static mastermind game with 2 pegs !
After this we will discuss a few results for more than 2 pegs !

A set of codes of a static mastermind game with m colors and n pegs which allows the codebreaker to give always the right answer is named static-code-set(m,n).
A static-code-set(m,n) with a minimum number of codes is called a optimal static-code-set(m,n).
The number of codes within a optimal static-code-set is called the Complexity C(m,n) !
We want to calculate now the C(m,2) for all m>=2 !

Following informations are known at the moment:
Table 1:

(? means, that a static-code-set ist known, but it is not known, if a better one exists.)

By the way: There is a nice applet on Cut The Knot, where you can calculate wether a set of codes is a static-code-set(m,n) or not !
We will often use this within the proofs.

Proposition 1
C(3k,2) < 2k for k > 1.
C(3k-1,2) < 2k für k > 1.
C(3k+1,2) < 2k+1 für k >1.

Proof:
We will construct a static-code-set:
a) C(3k,2) <= 2k ; k=1,2 is shown in the table above.
This code-set consists of k parts each with 2 Codes; each part contains 3 of the 3k colors; each color is located exactly in one of these parts:
part 1: (0,1) (0,2)
part 2: (3,4) (3,5)
....
part k: (3*(k-1) ,3*(k-1)+1) (3*(k-1) , 3*(k-1)+2)

It is easily shown with the applet, that part 1 and part 2 together is a static-code-set(6,2).
Each secret code gives an answer <> "00" in 1 or 2 parts, because each secret code consists of one or 2 colors.
But this 2 parts builds a static-code-set(6,2) ! q.e.d.
b) C(3k-1,2) <= 2k; k > 2.
Construct the static-code-set:
part 1: (0,1) (0,2) (0,3) (0,4)
part 2: (5,6) (5,7)
part 3: (8,9) (8,10)
and so on ...
Proof will be done as above (with the help of the applet for C(8,2) !) q.e.d.
c) C(3k+1,2) <= 2k+1; k > 2.
Construct the static-code-set:
part 1: (0,1) (0,2) (0,3)
part 2: (4,5) (4,6)
part 3: (7,8) (7,9)
and so on ...
Proof will be done as above (with the help of the applet for C(7,2) !) q.e.d.

Proposition 2:
An optimal Static-Code-Set(m,2) includes all m colors; m > 6

Proof:
Let us asume, that the color A is missing within an optimal static-code-set(m,2); m>=6.
In this case we will show that each of the other m-1 colors must be at position 1 of a code in the set.
Let us assume, that color 0 is never at position 1 (that means, there is no code (0,x) in this optimal static-code-set).
But then the secret codes (A,0) and (0,0) give the same answer ! ("10" for (x,0) and "00" otherwise; x<>A, x<>0).
That is not possible within a static-code-set !
So the assumption is wrong and each of the m-1 colors appears at least once at position one.
We have shown now, that our code-set (with missing color A) consists of at least m-1 codes !
But with Proposition 1 (and Table 1) we can show, that C(m,2) < m-1 for m>=6 !
(because m-C(m,2) >= k-1 >1 for k>=3)
This means, that our static-code-set(m,2) without the color A is not optimal !
The assumption, that the color A is missing within the optimal static-code-set(m,2), m>=6, is wrong ! q.e.d.

Proof:
For k=1,2 you can find the results in table 1. Now let k>=3 - in this case we can use Proposition 2.
a) C(3k-1,2) = 2k
Because of Proposition 1 we only have to show, that there is no Static-Code-Set(3k-1,2) with 2k-1 codes.
Let us assume, that there is an (optimal) statik-code-set(3k-1,2) with 2k-1 (or less) codes and all 3k-1 colors (Proposition 2).
We write down all 2k-1 codes, choose exactly one peg of each color within this codes and underline these 3k-1 pegs:
f.e.: (x1 , x2) (x3 , x4) (x5 , x6) .... (y , z)
Because there are 3k-1 pegs underlined within the 2k-1 codes(or less), there are at least k codes, where both pegs are underlined - and k-1 positions (or less),
which are not underlined (this k-1 positions can be used to repeat colors of the k underlined codes) . So there is at least 1 code (where both pegs are underlined) with 2 different colors ,
which are not repeated within the whole static-code-set - let this be the code (a , b) , a<>b.
But now we can easily see, that the static-code-set will give the same answers for the secret codes (a , a) and (b , b) !!
So the assumption that there is a static-code-set(3k-1,2) with 2k-1 codes was wrong !
b) C(3k,2) = 2k - same arguments as in a)
c) C(3k+1) = 2k+1 - same arguments as in a)
q.e.d.

Now we can complete the table 1:
Table 2 - C(m,2):

Analysis of static Mastermind with 2 pegs is now finished - but what about 3 or more pegs ?

First of all we want to construct a static-code-set for 3 pegs to get an upper limit for the complexity C(m,3):

Proof:
Like the proof of Proposition 1 we construct a Static-Code-Set(3k,3) with 3k codes.
This code-set consists of k parts each with 3 Codes; each part contains 3 of the 3k colors; each color is located exactly in one of these parts:
part 1: (0,1,2) (0,2,0) (2,1,1)
part 2: (3,4,5) (3,5,3) ((5,4,4)
part 3: (6,7,8) (6,8,6) (8,7,7)
....
part k: (3*(k-1) ,3*(k-1)+1,3*(k-1)+2) (3*(k-1) , 3*(k-1)+2,3*(k-1)) (3*(k-1)+2 , 3*(k-1)+1,3*(k-1)+1)

With the applet of [Cut The Knot] one can show, that the 3 codes of part 1, the 6 codes of part 1 and 2 and the 9 codes of part 1, 2 and 3 are static-code-sets(3k,3) !
Like in proposition1 this gives the proof !
q.e.d.

Hint:
Is there always a small number of i codes with j colors from which you can construct an optimal static-code-set(j*k,n) with C(j*k,n) = i*k , k>=1 ?
I think this is true, but there is no proof at the moment.
Bye the way - the static-code-set of Proposition 3 is not optimal, because C(6,3) <= 5.
Can you construct a static-code-set(6k,3) such that C(6k,3) <= 5k ?

We will now proof a lower bound for the Complexity - interesting for fixed number of pegs and large number of colors:

Hint:
Looking at two positions of a Static-Code-Set we will see, that there are never two colors a and b, missing in all codes at these positions !
Because otherwise the secret code (a,0,...,0,b,0,....,0) and (b,0,...,0,a,0,....,0) gives the same answer for all codes of the Static-Code-Set.

Proof of Proposition 4:
Let us look to a Static-Code-Set(m,n), with p< (m*(n-1)/n) - (n-1)/2 < m codes .
Let m > n*n/2 => q = m-p > n-1.
Look at each position and compute the number of missing colors within the codes at this position and be careful, that there are never missing the same two colors at any two positions.
Position 1: at least q colors missing;
Position 2: at least q-1 additional colors are missing (one color of position 1 can be repeated)
Position 3: at least q-2 additional colors missing
........
Position n: at least q-(n-1) additional colors missing
All these colors must be different; this means:
q + (q-1) + (q-2) + ... + (q-(n-1)) < m
n*q - n*(n-1)/2 < m
n*(m-p) -n*(n-1)/2 < m
m*(n-1) < n*(n-1)/2 + n*p < n*(n-1)/2 + m*(n-1) -n*(n-1)/2 = m*(n-1); this means, that the assumption p < (m*(n-1)/n) - (n-1)/2 was wrong !
q.e.d.

Example:
C(m,3) > 2m/3 -1 für m > 5
C(m,4) > 3m/4 - 1,5 für m > 8
C(m,5) > 4m/5 - 2 für m > 13

Proposition 5:
The assumption "|C(m,n+1) - C(m,n)| < 1 for all m,n > 2" is wrong !

Proof:
With Theorem 1 we get:: C(60,4) > 43,5
With Proposition 4 we get: C(60,2) = 40
The number of pegs increases by 2, but Complexity increases by more than 3 !
q.e.d.

Proposition 6:
C(m,n) < (m div 2)*(n+1) for all n,m > 2
(m div 2 is m/2 rounded down to next integer)

Proof:
For a fixed n let us construct a Static-Code-Set(2k,n) which is a Static-Code-Set(2k+1,n) as well:
Part 0 with n+1 codes: (0,0,...0) , (1,0,...,0) , (0,1,0,...,0) , ... , (0,0, ...,1)
Part 1 with n+1 codes: (2,2,...2) , (3,2,...,2) , (2,3,2,...,2) , ... , (2,2, ...,3)
.....
Part k-1 with n+1 codes: (2k-2,2k-2,...,2k-2) , (2k-1,2k-2,...,2k-2) , (2k-2,2k-1,2k-2,...,2k-2) , ... , (2k-2,2k-2,...,2k-1)
In each part there are exactly 2 colors a and b which do not appear in the other parts.
The first code within a part gives the number A of color a; with (a,a,...,a,b,a,...,a) with b at position i we get the following information:
Number of "blacks" = A-1 : there is color "a" at position i of the secret code
Number of "blacks" = A : there is neither color "a" nor color "b" at position i of the secret code
Number of "blacks" = A+1 : there is color "b" at position i of the secret code
q.e.d.

In parallel to my results Wayne Goddard analysed the Static Mastermind and got a lot of further interesting results; some of them I will repeat here.
He has solved the case of two positions, too - but furthermore he showed results for 3 and 4 positions and a lower bound for 5 or more positions.

Let S a Static-Code-Set(m,n) and let us construct a grid of cells - rows labeled by colors, columns labeled by positions - with a cross in a cell if that color
does not appear at that position. For a color i , let max(i) denote the maximum number of times color i is used in any one guess of S. Let cross(i) denote
the number of crosses in row i (that is, the number of positions in which color i never appears in S). Let occ(i) denote the total number of times i is used in S.
A color i confuses 2 positions, if each code of S that has i in the one position also has that color in the other position.

Proposition 7 (Wayne Goddard)
A) Ther cannot be two rows and two columns such that there are crosses in all 4 cells.
B) If colors i and j have crosses in the same column, then max(i) + max(j) > n.
C) For each pair of colors we have cross(i) + cross(j) < n.
D) Two different colors can´t confuse the same two positions..

Proof: See reference 6. q.e.d.

Wayne calculated the exact complexity of Static Mastermind with 3 and 4 positions:

Theorem 2 (Wayne Goddard)
A) C(m,3) = m - 1 for m > 5
B) C(m,4) = m - 1 for large m (f.e. m > 34*34)

Proof: See reference 6. q.e.d.

For 5 or more positions Wayne calculated the following lower bound:

Theorem 3 (Wayne Goddard)
For n > 5 there is a constant c_n>0 with C(m,n) > (1+c_n)m - O(1)

(Bye the way, this shows:
The assumption "|C(m+1,n) - C(m,n)| < 1 for all m,n > 2" is wrong !)

Proof: See reference 6.
For n=5 I will show the proof of Wayne and will compute the constant c₅.

Let us analyse the colors with occ(i) < 5 and count them:
a) There is a maximum of 5*4/2 = 10 colors with cross(i) > 2, because of proposition 7A).
b) Find the colors which confuses 2 positions. Because of proposition 7D) there are at most 10 such colors.
c) Let cross(i) = 1, that means the color i does not appear at one position.
For 2 colors i and j, which do not appear at the same position, we get with 7B) : max(i) + max(j) > 5.
One of these colors, say i, has max(i) > 3. Because cross(i) = 1 and occ(i) < 5 , such a color confuses 2 or more positions.
But we counted these colors in b) !
So we have to count here only 1 color for each position - 5 colors !
d) Find the colors i with cross(i) = 0 (and occ(i) < 5), which don´t confuse 2 positions.
These colors appear in five codes - at a different position in each code; such colors are named flat.
Let 1, 2 and 3 be flat colors and (1,2,a,b,c) and (3,1,x,y,z) two codes in the Static-Code-Set.
In this case one cannot distinguish between the codes (1,1,1,2,3) and (3,2,1,2,3) ! (Even if color 3 = color 2)
Within the 25 pegs in the 5 codes of a flat color there are at most 15 ( = 60%) which belongs to flat colors !
Because of a) b) c) there are at most 25 (independent of the number m of colors) not flat colors with occ(i) < 5.
So we get a constant c₅ = 1/5 (2/5 * 6 + 3/5 *5) = 1,08.
q.e.d.

Colors	2	3	4	5	6	7	8	9	10
Complexity	2	2	3	4	4	5	6?	6?	7?

Colors	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	.....
Complexity	2	2	3	4	4	5	6	6	7	8	8	9	10	10	11	12	12	13	14	14	.....

(Static-)Mastermind