(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:**

Colors | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |

Complexity | 2 | 2 | 3 | 4 | 4 | 5 | 6? | 6? | 7? |

(? 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 1C(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 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).

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.

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

__Proof:
__Let us asume

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.

Theorem 1:C(3k,2) = 2kC(3k-1,2) = 2k C(3k+1,2) = 2k+1 for k > 1 |

__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.: (

Because there are 3k-1 pegs underlined within the 2k-1 codes(or less), there are

which are not underlined (this

which are not repeated within the whole static-code-set - let this be the code (

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:

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 | ..... |

**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):

Proposition 3:C(3k,3) < 3k für k>1. |

__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 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.

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:

Proposition 4:C(m,n) > (m*(n-1)/n) - (n-1)/2 for all n > 2 , m >
n*n/2 |

**Hint:
**Looking

__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)

C(m,4)

C(m,5)

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.

Some new results by Wayne Goddard
(May 2002) |

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.

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:

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:

> 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_{5}.

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_{5} = 1/5 (2/5 * 6 + 3/5 *5) = 1,08.

q.e.d.

**References:**

1. Invitation to Mastzermind/Cut
The Knot (Don Greenwell/Alex Bogomolny)

2. Investigations into the Master
Mind^{TM} Board Game (Toby Nelson)

3. V. Chvatal, Mastermind, Combinatorica 3 (1983), 325-329

4. -

5. Static Mastermind by
Don Greenwell

6. Static Mastermind by Wayne Goddard

7. Mastermind Revisited by Wayne Goddard

8. Mastermind by Petr Felzmann (Link
broken)

**Update of References(April 2011):**

9. Optimal Algorithms for 2xn AB Games by
SHAN-TAI CHEN AND SHUN-SHII LIN(2003)

10.A
Two-Phase Optimization Algoritm for Mastermind by SHAN-TAI CHEN1, SHUN-SHII LIN2 AND LI-TE HUANG(2006)

11.Mastermind is NP-Complete by Jeff Stuckman and Guo-Qiang Zhang (2006)

12.Efficient solutions for Mastermind using
genetic algorithms by Lotte Berghman, Dries Goossens, Roel
Leus (2009)

13.Optimal Analyses for 3xn AB Games in the Worst Case
by Li-Te Huang and Shun-Shii Lin (2009)

14.The number of pessimistic guesses in Generalized
Mastermind by Gerold Jäger and Marcin Peczarski (2009)

(19.04.11 G. Rosenbaum , Last Update:
19.4.11, My Homepage: Guenthers 3M
Collectors Homepage)