Mastermind

(Februar 2002)
Das Spiel Mastermind ist wohl den meisten bekannt:
Ein Mitspieler wählt aus 6 Farben einen 4-stelligen Geheimcode aus; d.h. er wählt einen aus 6**4 Codes aus.
Der 2-te Spieler muß diesen Code erraten, indem er einen Code vorgibt und darauf von Spieler 1 folgende Informationen bekommt:
- Die Anzahl der Codestellen, die in Position und Farbe richtig sind ("schwarze Antwort-Stifte").
- Die Anzahl der weiteren Codestellen, deren Farbe richtig ist, deren Position aber falsch ist ("weiße Antwort-Stifte).
Anhand dieser Informationen muß der 2-te Spieler (der "Codebrecher") in möglichst wenig Versuchen den Geheimcode erraten !
Man kann zeigen, daß dieses klassische Mastermind immer in 5 oder weniger Zügen lösbar ist (d.h. man hat die Lösung nach 4 Zügen und
der 5-te Zug besteht eben aus der Vorgabe dieser richtigen Lösung).
Die erwartete durchschnittliche Anzahl von Zügen bei dieser Strategie ist 4,478 !
Nimmt man in Kauf, daß in seltenen Fällen auch 6 Züge benötigt werden, so kann die durchschnittliche Anzahl von Zügen sogar auf 4,34 Züge reduziert werden.

Das ganze Spiel läßt sich dann natürlich erweitern auf m Farben und n Stellen !

Siehe hierzu auch:
Static Mastermind von Don Greenwell

Statik-Mastermind:
Der Codebrecher muß nun alle seine Vermutungen auf einmal abgeben;
er bekommt dann auch alle Antworten auf einmal und muß anhand dieses Ergebnisses den Geheimcode bestimmen.
Eine Menge von Codes des Mastermind-Spieles mit m Farben und n Stellen, die die Bestimmung eines jeden Geheimcodes ermöglicht,
nennen wir nun einen Statik-Code-Set(m,n).
Die Menge aller Codes ist natürlich auch ein Statik-Code-Set(m,n), denn auf genau einen Code bekommt man die Antwort "n Schwarze" - (0,n).
Dieser Code ist dann der gesuchte !
Allerdings ist diese Menge recht langweilig - daher liegt es nahe, eine minimale Menge von Codes zu finden, die einen Statik-Code-Set(m,n) bilden !
Die minimale Anzahl von Codes zur Lösung des Statik-Mastermind Problems nennen wir dann auch die Komplexität des Spieles: C(m,n);
einen Statik-Code-Set(m,n) mit dieser minimalen Anzahl von Codes nennen wir auch "optimalen Statik-Code-Set(m,n)".

Das Ziel der folgenden Ausführungen soll dann sein,
die Komplexität C(m,2) allgemein für alle m=1,2..... zu bestimmen !

Beispiel 1:
Nehmen wir das Mastermindspiel mit 4 Farben und 2 Stellen und bestimmen wir einen Statik-Code-Set(4,2) und die Komplexität C(4,2).
Die Farben seien 0,1,2 und 3 . Mögliche Antworten bei einem Versuch sind: 00, 10, 01, 20, 02
Statik-Code-Set = ((0,1), (2,3), (2,1))
Die Antworten auf die 16 verschiedenen Geheimcodes sind (Schwarze Weiße):
(0,0) = 10-00-00      (1,0) = 02-00-01       (2,0) = 01-10-10       (3,0) = 01-01-00
(0,1) = 20-00-10      (1,1) = 10-00-10      (2,1) = 10-10-11       (3,1) = 10-01-10
(0,2) = 10-01-01      (1,2) = 01-01-02       (2,2) = 00-10-10       (3,2) = 00-02-01
(0,3) = 10-10-00      (1,3) = 01-10-01       (2,3) = 00-11-10       (3,3) = 00-10-00
Die 16 Antworttripel sind allesamt unterschiedlich - man kann also eineindeutig von der Antwort auf den Geheimcode schließen !
Damit ist klar, daß die 3 Codes einen Statik-Code-Set(4,2) bilden - wir kennen allerdings noch nicht den Wert C(4,2);
allerdings gilt C(4,2) <= 3, da wir oben ja schon einen Beispielcode konstruiert haben.
Ein Applet, welches ziemlich einfach prüft, ob eine Menge von Codes einen Statik-Code-Set bilden, findet man auf [Cut The Knot].
Man kann allerdings mit diesem Applet nicht bestimmen, ob die Codes optimal sind !
Auf der gleichen Homepage findet man auch eine Tabelle mit den derzeit bekannten Komplexitäten C(m,n); dort sieht man C(4,2) = 3.
Dies kann man dadurch beweisen, indem man alle 256 möglichen Code-Paare wie im Beispiel oben prüft (z.B. mit dem PC) und erkennt,
daß mindestens 2 Codes zu den gleichen Antworten führen.
Wir können dies aber auch direkt beweisen. Anbei noch die laut [Cut The Knot] bekannten Werte für C(m,2):

Tabelle 1:

(? bedeutet hier, daß die Optimalität noch nicht bewiesen ist. Der Beweis wird auf dieser Seite aber erbracht.)

Beispiel 2:
Ein Beispiel für ein Statik-Code-Set(6,2) ist : ((0,1), (0,2) , (3,4), (3,5)).
Dies beweist man wie oben oder einfach durch das oben beschriebene Applet.

Beweis:
Der Beweis wird hier zur Einstimmung direkt geführt.
Hinweis: Ein Statik-Code-Set behält diese Eigenschaft, wenn man die Reihenfolge der Codes innerhalb der Menge ändert,
wenn man die Farben neu nummeriert und wenn man die Postitionen neu nummeriert. Natürlich auch, wenn man zusätzliche Codes hinzufügt.
a) Falls C(4,2) = 1, so besteht der Statik-Code-Set o.B.d.A.(Umnummerierung der Farben) aus (0,a) , a=0,1.
Die Codes (2,3) und (3,2) liefern als Antwort beide "00" auf die Frage (0,a); also ist (0,a) kein Statik-Code-Set.
Also C(4,2) >= 2 !
b) Wir müssen nun also noch die Behauptung C(4,2) = 2 widerlegen.
Nehmen wir also an, daß (a,b) (c,d) ein Statik-Code-Set(4,2) wäre.
b1) Wenn in den beiden Codes nur 1 oder 2 der 4 Farben auftauchen, so kann wie unter a) ein Widerspruch hergeleitet werden.
b2) Wenn in den 2 Codes alle 4 Farben auftauchen, so können wir o.B.d.A. von (0,1) (2,3) ausgehen.
In diesem Fall sind aber wiederum die Geheimcodes (2,1) und (0,3) mit der gemeinsamen Antwort "10-10" nicht unterscheidbar;
also ist dies kein Statik-Code-Set.
b3) Wir nehmen also nun an, daß in den 2 Codes genau 3 der 4 Farben enthalten sind.
Die 2 Codes sind nun o.B.d.A. (0,1) (2,a) mit a=0,1,2.
- (0,1) (2,0) : (3,1) und (1,1) liefern beide die Antwort "10-00"
- (0,1) (2,1) : (0,3) und (0,0) liefern beide die Antwort "10-00"
- (0,1) (2,2) : (0,3) und (0,0) liefern beide die Antwort "10-00"
also bildet auch (0,1) (2,a) mit a=0,1,2 keinen Statik-Code-Set.
Also: Da wir schon einen Statik-Code-Set mit 3 Codes gebildet haben und wir jetzt gezeigt haben, daß 2 Codes nicht ausreichen,
gilt also: C(4,2) = 3 . q.e.d.

Behauptung 2:
In einem Statik-Code-Set(m,2) sind mindestens m-1 Farben enthalten; m >= 3.
Allgemein: In einem Statik-Code-Set(m,n) sind mindestens m-1 Farben enthalten; m>=3, n>=2.

Beweis:
Nehmen wir an, die 2 unterschiedlichen Farben a und b würden in einem Statik-Code-Set(m,2) vollständig fehlen.
Dann würden die Geheimcodes (a,b) und (b,a) beide die Antwort "00-00...-00" liefern - also nicht unterscheidbar sein.
Dies wäre ein Widerspruch; also müssen mindestens m-1 Farben enthalten sein.
Die allgemeine Argumentation ist analog: (a,b,0,...,0) und (b,a,0,...,0) liefern beide dieselbe Antwort.

Behauptung 3:
Es gibt Statik-Code-Sets(m,2) mit genau m-1 Farben; m >=3.

Bemerkung:
Es wird nicht behauptet, daß diese Statik-Code-Sets optimal sind.
Es soll nur gezeigt werden, daß wir uns bei den späteren Überlegungen nicht auf den (einfacheren) Fall beschränken können,
daß alle Farben in dem Statik-Code-Set(m,2) enthalten sind.

Beweis:
Die m Farben seien 0,1,...m-1.
Wir konstruieren folgenden Statik-Code-Set(m,2) ohne die Farbe m-1 bestehend aus 2m-3 Codes:
(0,0) (0,1) ... (0,m-2) (1,0) (2,0) ... (m-2,0).
Wir zeigen nun, daß wir jeden Geheimcode rekonstruieren können:
Die Häufigkeit der Farbe 0 erkennen wir an der Antwort auf (0,0).
a) Farbe 0 ist 2mal vorhanden : Dann ist der Geheimcode (0,0)
b) Farbe 0 ist nicht vorhanden: Dann zeigen mir die Antworten auf (0,1)...(0,m-2), welche Farbe von 1 bis m-2 an Stelle 2 vorkommt.
Wenn keine dieser Farben vorkommt, dann ist es die Farbe m-1.
Die Info für die Stelle 1 des Geheimcodes liefern mir analog dieAntworten auf (1,0)...(m-2,0).
c) Farbe 0 ist genau 1mal vorhanden: Dann liefert (0,1) oder (1,0) mindestens einen Schwarzen in der Antwort.
Nehemen wir an es wäre (0,1) (gleiche Argumentation bei (1,0)).
Dann liefert die Reihe (0,1)...(0,m-2) entweder immer die Antwort "10" - dann ist der Geheimcode (0,m-1) - , oder genau einmal "20" - dann ist dieses der gesuchte Geheimcode. q.e.d.

Bemerkung:
Wir betrachten hier also vorerst nur die Fälle, wo die Anzahl der Farben durch 3 teilbar ist.
Die fehlenden Fälle werden dann noch anschließend diskutiert.
(k=1 ist trivial).

Beweis (k>=2):
Um C(3k,2) <= 2k zu beweisen, konstruieren wir uns ein entsprechendes Statik-Code-Set mit 2k Codes.
Dieser Code-Set besteht aus k Bereichen mit jeweils 2 Codes; jeder Bereich enthält genau 3 der insgesamt 3k Farben;
jede Farbe kommt also in genau nur einem Bereich vor:
Bereich 1: (0,1) (0,2)
Bereich 2: (3,4) (3,5)
....
Bereich k: (3*(k-1) ,3*(k-1)+1) (3*(k-1) , 3*(k-1)+2)
Zeigen wir nun, daß wir hiermit jeden Code entschlüsseln können:
Der Geheimcode besteht aus einer oder 2 Farben, liefert also höchstens in 2 Bereichen eine Antwort ungleich "00", da jede Farbe ja nur in genau einem Bereich vorkommt.
Dieser eine oder die 2 Bereiche lassen sich durch Umnummerierung der Farben exakt auf das Beispiel 2 von oben abbilden, von dem wir
ja schon bewiesen haben, daß es ein Statik-Code-Set ist. Damit haben wir also gezeigt, daß wir mit dem konstruierten Code-Set jeden Geheimcode entschlüsseln können.
Also ist C(3k,2) <= 2k.

Nun müssen wir noch beweisen, daß man keine Statik-Code-Sets(3k,2) mit weniger als 2k Codes konstruieren kann !
Wir nehmen also an, daß es einen Statik-Code-Set(3k,2) mit 2k-1 Codes gibt.
Unsere Behauptung 2 zeigt, daß dieser Code aus 3k oder 3k-1 Farben besteht.
Fall 1: Alle 3k Farben sind im Statik-Code-Set enthalten.
In der Menge der 2k-1 Codes wählen wir nun von jeder der 3k unterschiedlichen Farben genau einen Vertreter aus und unterstreichen diesen:
z.B.: (x1 , x2) (x3 , x4) (x5 , x6) .... (y , z)
Da wir nun 3k Unterstreichungen in den 2k-1 Codes durchgeführt haben, gibt es mindestens k+1 Codes, in welchen beide Positionen unterstrichen
sind und k-2 Positionen, die nicht unterstrichen wurden (und bei denen dann Farbwiederholungen auftreten).
Selbst wenn ich jetzt mit den k-2 nicht unterstrichenen Farbwiederholungen viele der Farben aus den k+1 Codes (in welchen beide Positionen unterstrichen sind)
wiederhole - es bleiben mindestens 3 Codes (a , b) (c , d) (e , f) übrig, deren 6 verschiedene Farben nur genau einmal im Statik-Code-Set vorkommen.
Dies ist aber sofort ein Widerspruch, da jetzt die Geheimcodes (a , a) und (b , b) nicht mehr unterscheidbar sind (beide liefern genau an derselben Stelle eine "10" und
sonst nur "00").

Fall 2: Nur 3k-1 Farben sind im Statik-Code-Set enthalten.
Die Argumentation läuft identisch zu oben. Es gibt jetzt mindestens k Codes, in welchem beide Positionen unterstrichen sind und k-1 Positionen, die nicht unterstrichen sind.
Also gibt es hier mindestens einen Code (a , b), dessen 2 verschiedene Farben genau einmal im Statik-Code-Set vorkommen. Dies führt zum gleichen Widerspruch.

Damit haben wir also die Annahme, daß es einen Statik-Code-Set(3k,2) mit 2k-1 Codes gibt, zum Widerspruch geführt ! q.e.d.

Beweis:
K = 1 ist klar. Sei k >=2.
a) Um C(3k-1,2) <= 2k zu beweisen, konstruieren wir uns ein entsprechendes Statik-Code-Set mit 2k Codes.
Dieser Code-Set besteht aus einem Startbereich mit 4 Codes(mit 5 Farben) und k-1 Bereichen mit jeweils 2 Codes; jede Farbe kommt in genau nur einem Bereich vor:
Bereich 1: (0,1) (0,2) (0,3) (0,4)
Bereich 2: (5,6) (5,7)
Bereich 3: (8,9) (8,10) , usw.
Mit dem Applet zeigt man wieder, daß Bereich 1 einen Statik-Code-Set(5,2) bildet und Bereich 1 und Bereich 2 zusammen einen Statik-Code-Set(8,2).
Wie bei Behauptung 4 sieht man also wieder, daß wir so einen Statik-Code-Set(3k-1,2) konstruiert haben.

b) Um C(3k+1,2) <= 2k+1 zu beweisen, konstruieren wir uns ein entsprechendes Statik-Code-Set mit 2k+1 Codes.
Dieser Code-Set besteht aus einem Startbereich mit 3 Codes(mit 4 Farben) und k-1 Bereichen mit jeweils 2 Codes; jede Farbe kommt in genau nur einem Bereich vor:
Bereich 1: (0,1) (0,2) (0,3)
Bereich 2: (4,5) (4,6)
Bereich 3: (7,8) (7,9) , usw.
Mit dem Applet zeigt man wieder, daß Bereich 1 einen Statik-Code-Set(4,2) bildet und Bereich 1 und Bereich 2 zusammen einen Statik-Code-Set(7,2).
Wie bei Behauptung 4 sieht man also wieder, daß wir so einen Statik-Code-Set(3k+1,2) konstruiert haben.
q.e.d.

Für die folgenden Beweise brauchen wir noch eine Verschärfung der Behauptung 2:

Behauptung 6:
In einem optimalen Statik-Code-Set(m,2) sind alle m Farben enthalten; m >= 6

Beweis:
Nehmen wir an, wir hätten einen optimalen Statik-Code-Set(m,2) in welchem die Farbe a nicht enthalten ist.
Behauptung: Jede der anderen m-1 Farben muß mindestens einmal an der Position 1 eines Codes auftreten !
Denn wenn z.B. die Farbe 0 nie an Position 1 auftaucht (d.h. es gibt keine Codes (0,x) in diesem Statik-Code-Set),
so sind die Geheimcodes (a,0) und (0,0) nicht unterscheidbar ! (sie liefern als Antwort "10" bei (x,0) und "00" sonst; x<>a, x<>0).
Da also alle Farben außer einer mindestens einmal an Position 1 auftauchen müssen, enthält unser Statik-Code-Set(m,2)
mindestens m-1 Codes !
Wir haben aber für m>=6 schon in Behauptung 4 und 5 Statik-Code-Sets konstruiert, die weniger als m-1 Codes enthalten!
Dies ist ein Widerspruch zur Optimalität des Statik-Code-Sets !
Damit müssen also alle Farben in einem optimalen Statik-Code-Set(m,2), m>=6, enthalten sein !
q.e.d.

Bemerkung:
Diese Behauptung kann man vermutlich verallgemeinern für optimale Statik-Code-Sets(m,n) mit großem m und kleinem n.

Beweis:
Für k=1,2 ist diese Aussage schon bewiesen (siehe Tabelle am Anfang).
Auch C(3k-1,2) <= 2k haben wir in Behauptung 5 schon bewiesen.
Sei k>= 3, dann gilt auch Behauptung 6.
Wir nehmen also an, C(3k-1,2)<= 2k-1. Es gibt also ein Statik-Code-Set(3k-1,2) mit höchstens 2k-1 Codes in welchem alle Farben enthalten sind.
Wie in Behauptung 4 gehen wir nun vor:
In der Menge der 2k-1 Codes wählen wir nun von jeder der 3k-1 unterschiedlichen Farben genau einen Vertreter aus und unterstreichen diesen:
z.B.: (x1 , x2) (x3 , x4) (x5 , x6) .... (y , z)
Da wir nun 3k-1 Unterstreichungen in den 2k-1 Codes durchgeführt haben, gibt es mindestens k Codes, in welchen beide Positionen unterstrichen
sind und k-1 Positionen, die nicht unterstrichen wurden (und bei denen dann Farbwiederholungen auftreten).
Selbst wenn ich jetzt mit den k-1 nicht unterstrichenen Farbwiederholungen viele der Farben aus den k Codes (in welchen beide Positionen unterstrichen sind)
wiederhole - es bleibt mindestens 1 Codes (a , b) übrig, dessen 2 verschiedene Farben nur genau einmal im Statik-Code-Set vorkommen.
Dies ist aber sofort ein Widerspruch, da jetzt die Geheimcodes (a , a) und (b , b) nicht mehr unterscheidbar sind (beide liefern genau an derselben Stelle eine "10" und
sonst nur "00"). q.e.d.

Beweis:
Wie oben zeigen wir für einen Statik-Code-Set(3k+1,2) mit höchstens 2k Codes und allen Farben; k>=3:
Wir machen 3k+1 Unterstreichungen in 2k Codes; es gibt mindestens k+1 Codes, in welchem beide Positionen unterstrichen sind und k-1 Positionen, die
nicht unterstrichen wurden. Damit bleiben mindestens 2 Codes übrig, deren 4 verschiedene Farben nur genau einmal vorkommen, was sofort wieder
zum Widerspruch führt. q.e.d.

Damit können wir Tabelle 1 ergänzen:

Tabelle 2:

Damit haben wir die Komplexität für alle Statik-Code-Set(m,2) exakt bestimmt !!

Für Statik-Mastermind mit mehr als 2 Stellen wird die Sache nun bedeutend schwieriger.
Zumindestens kann man versuchen, einen Statik-Code-Set(m,k) zu konstruieren, um eine obere Schranke für die Komplexität zu erhalten:

Beweis:
Ähnlich zu den Beweisen mit 2 Stellen konstruieren wir wieder ein Statik-Code-Set(3k,3) mit 3k Codes.
Dieser Code-Set besteht aus k Bereichen mit jeweils 3 Codes; jeder Bereich enthält genau 3 der insgesamt 3k Farben;
jede Farbe kommt also in genau nur einem Bereich vor (die Struktur jedes Bereiches ist identisch !):
Bereich 1: (0,1,2) (0,2,0) (2,1,1)
Bereich 2: (3,4,5) (3,5,3) ((5,4,4)
Bereich 3: (6,7,8) (6,8,6) (8,7,7)
....
Bereich 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)

Mit dem Applet auf [Cut The Knot] kann man nun wieder nachweisen, daß die 3 Codes aus Bereich 1, die 6 Codes aus Bereich 1+2 und die 9 Codes aus Bereich 1+2+3
jeweils wieder ein Statik-Code-Set(3k,3) bilden. Da ein beliebiger Geheimcode wieder maximal in 3 Bereichen eine Antwort ungleich "00" liefert, und diese 3 Bereiche
auf einen Statik-Code-Set(9,3) abbildbar sind, ist alles bewiesen.
q.e.d.

Bemerkung:
Gibt es immer eine kleine Anzahl von i Codes mit j Farben aus denen man einen optimalen Statik-Code-Set(j*k,n) mit C(j*k,n) = i*k , k>=1, bilden kann ?
Ich glaube ja - aber der Beweis ist noch ausstehend.
Der Statik-Code-Set aus Behauptung 9 ist nicht optimal, denn C(6,3) <= 5.
Kann man einen Statik-Code-Set konstruieren mit C(6k,3) <= 5 ?? Ist dieser optimal ??

Bemerkung:
Betrachtet man in einem Statik-Code-Set alle Farben, welche an einer festen Position vorkommen, so dürfen nie die zwei gleichen Farben, z.B. a und b, an zwei unterschiedlichen Positionen fehlen.
Anderenfalls wären die Geheimcodes (a,0,...,0,b,0,....,0) und (b,0,...,0,a,0,....,0) nicht unterscheidbar !

Beweis der Behauptung 10:
Betrachten wir nun einen Statik-Code-Set(m,n), welcher p< (m*(n-1)/n) - (n-1)/2 < m Codes enthält .
Sei m > n*n/2 und damit q = m-p > n-1.
Betrachten wir nun die einzelnen Positionen und berechnen die Mindestanzahl der fehlenden Farben innerhalb aller Codes an dieser Position unter der Voraussetzung, daß an zwei Positionen nie die gleichen Farben fehlen !
Position 1: mindestens q Farben fehlen; von diesen Farben darf maximal je eine an den anderen Positionen fehlen.
Position 2: mindestens q-1 weitere Farben fehlen (eine kann ja auch an Position 1 schon fehlen)
Position 3: mindestens q-2 weitere Farben fehlen
........
Position n: mindestens q-(n-1) weitere Farben (müßten) fehlen
Damit alle diesen Farben unterschiedlich sind muß gelten:
q + (q-1) + (q-2) + ... + (q-(n-1)) < m d.h.
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); also ein Widerspruch für p < (m*(n-1)/n) - (n-1)/2
q.e.d.

Beispiele:
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

Behauptung 11:
Die Vermutung "|C(m,n+1) - C(m,n)| < 1 für alle m,n > 2" ist falsch !

Beweis:
Mit Behauptung 10 gilt: C(60,4) > 43,5
Mit Behauptung 4 gilt: C(60,2) = 40
Die Anzahl der Stellen steigt nur um 2, die Komplexität aber um mehr als 3 !
q.e.d.

Behauptung 12:
C(m,n) < (m div 2)*(n+1) für alle n,m > 2
(div ist hier die Integerdivision)

Beweis:
Für ein festes n konstruieren wir uns wieder einen Statik-Code-Set(2k,n), welcher auch gleichzeitig ein Statik-Code-Set(2k+1,n) ist::
Bereich 0 aus n+1 Codes: (0,0,...0) , (1,0,...,0) , (0,1,0,...,0) , ... , (0,0, ...,1)
Bereich 1 aus n+1 Codes: (2,2,...2) , (3,2,...,2) , (2,3,2,...,2) , ... , (2,2, ...,3)
.....
Bereich k-1 aus 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 jedem Bereich sind nur 2 Farben a und b vorhanden.
Der erste Code gibt die Anzahl der Farbe a im Geheimcode vor(Anzahl Schwarze = A); durch (a,a,...,a,b,a,...,a) mit einem b an Stelle i erhält man
folgende Information:
Anzahl Schwarze = A-1 : der Geheimcode enthält an dieser Position ein a
Anzahl Schwarze = A : der Geheimcode enthält an dieser Position weder ein a noch ein b (die anderen Bereiche liefern hierfür die Info)
Anzahl Schwarze = A+1 : der Geheimcode enthält an dieser Position ein b

Für ungerade Anzahl Farben ergibt sich dann die letzte Farbe automatisch dadurch, daß keine der anderen Farben an dieser Position bestimmt werden konnte.
q.e.d.

Wayne Goddard hat parallel zu meinen Ausführungen auch das Static Mastermind analysiert und ist zu weiteren interessanten Ergebnissen gekommen,
welche ich hier teilweise zitieren möchte. Er hat auch den Fall von 2 Positionen gelöst, allerdings dann noch die Fälle von 3 und 4 Positionen und eine generelle
Aussage für 5 oder mehr Positionen.

Sei ein Static-Code-Set(m,n) gegeben und konstruieren wir eine Matrix von Zellen - pro Farbe eine Zeile und pro Position eine Spalte - mit einem Kreuz
in einer Zelle, wenn diese Farbe niemals an dieser Position auftaucht. Für eine Farbe i bezeichne max(i) wie häufig die Farbe i maximal in jedem Code des
Static-Code-Sets auftaucht. Sei cross(i) die Anzahl der Kreuze in Zeile i der Matrix (d.h. die Anzahl der Positionen in welcher die Farbe i niemals auftaucht).
occ(i) bezeichne wie häufig die Farbe i in allen Codes auftaucht.
Eine Farbe i verwirrt 2 Positionen, wenn jeder Code des Static-Code-Sets die Farbe i an beiden Positionen besitzt oder an keiner der beiden Positionen die
Farbe i vorhanden ist.

Behauptung 13 (Wayne Goddard)
A) Es gibt keine 2 Zeilen und 2 Spalten mit Kreuzen in allen 4 Zellen.
B) Wenn die Farben i und j Kreuze in den gleichen Spalten haben, dann gilt max(i) + max(j) > n.
C) Für jedes Paar von 2 Farben gilt cross(i) + cross(j) < n.
D) Zwei Farben können nie die zwei gleichen Positionen verwirren.

Beweis: Siehe Referenz 6. q.e.d.

Wayne berechnet dann exakt die Komplexität des Static Mastermind mit 3 und 4 Positionen:

Behauptung 14 (Wayne Goddard)
A) C(m,3) = m - 1 für m > 5
B) C(m,4) = m - 1 für genügend große m (z.B. m > 34*34)

Beweis: Siehe Referenz 6. q.e.d.

Für 5 oder mehr Positionen zeigt Wayne noch folgende untere Schranke:

Behauptung 15 (Wayne Goddard)
Für n > 5 gibt es eine Konstante c_n>0 mit C(m,n) > (1+c_n)m - O(1)

Beweis: Siehe Referenz 6.
Für n=5 möchte ich den Beweisgang von Wayne hier kurz andeuten und die Konstante c bestimmen:

Wir betrachten nun die Farben mit occ(i) < 5 und zählen diese.
a) Hiervon gibt es höchstens 5*4/2 = 10 Farben mit cross(i) > 2, wegen Behauptung 13A).
b) Betrachten wir die Farben, welche 2 Positionen verwirren. Auch hiervon kann es nach Behauptung 13D) höchstens 10 Farben geben.
c) Sei cross(i) = 1, d.h. die Farbe i taucht an genau einer Position nicht auf.
Für 2 Farben i und j, welche an genau derselben Position nicht auftauchen, gilt nach 13B) : max(i) + max(j) > 5.
Für eine dieser Farben, z.B. i, gilt also max(i) > 3. Da cross(i) = 1 und occ(i) < 5 , verwirrt eine solche Farbe also mindestens 2 Positionen.
Solche Farben haben wir aber schon unter b) gezählt.
Es muß hier also nur noch pro Position 1 Farbe gezählt werden - also 5 Farben.
d) Betrachten wir nun die Farben mit cross(i) = 0 (und occ(i) < 5), welche außerdem keine 2 Positionen verwirren (denn diese haben wir ja schon unter b) gezählt).
Solche Farben tauchen genau einmal an jeder Position auf - und jedesmal in einem anderen Code; also in genau 5 Codes; solche Farben nennen wir "flat".
Seien nun 1, 2, und 3 solche Farben und (1,2,a,b,c) und (3,1,x,y,z) zwei Codes im Static-Code-Set.
Dann kann man nicht zwischen den Codes (1,1,1,2,3) und (3,2,1,2,3) unterscheiden ! (Das gleiche gilt, wenn Farbe 3 = Farbe 2 ist).
In den 25 Positionen in den 5 Codes zu einer festen "flat" Farbe können also höchstens 15 ( = drei Fünftel) zu einer "flat" Farbe gehören.
Nach a), b), c) gibt es noch höchstens 25 (von der Anzahl Farben m unabhängig) nicht "flat" Farben mit occ(i) < 5.
Also erhalten wir für die Konstante c₅ = 1/5 (2/5 * 6 + 3/5 *5) = 1,08.
q.e.d.

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

(Statik-)Mastermind