Ich habe einen anderen Beweis, dass mindestens (m-1)(n-1) + 2 Karten immer abgelegt werden können.
Der Beweis funktioniert mit Induktion nach n und m. Wenn n = 2 (der Fall m = 2 geht natürlich genauso), gibt es nur zwei Farben und mindestens m + 1 Karten. Ein Symbol x muss also in beiden Farben vorkommen. Spiele nun alle Karten außer x in der einen Farbe, dann beide x-Karten, dann die der anderen Farbe.
Seien nun m, n >= 3. OBdA ist m <= n (sonst vertausche die Rollen von Farben und Symbolen). Von den m*n möglichen Karten fehlen höchstens m + n - 3 < 2n. Es muss also eine Farbe geben, von der höchstens eine Karte aussortiert wurde. Ansonsten würden ja mindestens zwei Karten pro Farbe fehlen, also insgesamt 2n. Sei nun f eine solche Farbe.
Fall 1: Alle m Karten der Farbe f sind vorhanden.
Entferne alle f-Karten und füge eine beliebige fehlende Karte x einer anderen Farbe hinzu (wenn es eine solche gibt). Dann hat man eine Situation mit m Symbolen, n-1 Farben und mindestens (m-1)(n-1)+2 - m + 1 = (m-1)(n-2)+2 vorhandenen Karten. Nach Induktion können diese Karten alle hintereinander abgelegt werden. Wähle eine Abfolge der Karten, mit der dies möglich ist.
Fall 1a: x ist erste oder letzte Karte der Abfolge, oder x wird zwischen zwei Karten mit dem gleichen Symbol gespielt.
Dann kann x aus der Abfolge entfernt werden, die Abfolge bleibt zulässig. Füge am Ende noch die Karten der Farbe f an (erst die mit dem gleichen Symbol wie die bisher letzte Karte, dann die anderen in beliebiger Reihenfolge). Das ergibt eine gültige Abfolge der anfangs gegebenen Karten.
Fall 1b: x wird zwischen zwei Karten mit verschiedenen Symbolen gespielt.
Ordne die Karten der Farbe f so an, dass die erste das gleiche Symbol hat wie die Karte vor x und die letzte das gleiche Symbol wie die Karte nach x. Ersetze x durch diese Abfolge und erhalte wieder eine zulässige Ablagereihenfolge.
Fall 2: Von Farbe f fehlt nur das Symbol s.
Entferne alle f-Karten. Dann hat man mindestens (m-1)(n-1) + 2 - (m-1) = (m-1)(n-2) + 2 Karten in n-1 Farben mit m Symbolen. Nach Induktion können diese Karten zu einer gültigen Ablagefolge angeordnet werden. Wähle eine solche Folge.
Fall 2a: Die erste oder letzte Karte dieser Folge hat nicht das Symbol s.
Dann gibt es eine f-Karte die direkt vor oder direkt nach der Folge ohne f abgelegt werden kann. Füge schließlich die restlichen f-Karten am Anfang bzw. am Ende an und erhalte eine gültige Ablagefolge.
Fall 2b: Die erste und letzte Karte tragen beide das Symbol s.
Dann passen erste und letzte Karte aneinander. Man kann also an einer beliebigen Stelle die Ablagefolge beginnen, bis zum Ende durchspielen und dann am Anfang beginnen, um die restlichen Karten abzulegen. Insbesondere kann man so erreichen, dass die Sequenz mit einem Symbol ungleich s endet. Ansonsten gab es nur s- und f-Karten am Anfang, ohne die Karte (f, s). Das wären maximal m + n - 2 < m+n-2 + (m-2)(n-2) + 1 = (m-1)(n-1) + 2. Nach dieser Umsortierung weiter wie in 2a.
Der Beweis funktioniert mit Induktion nach n und m. Wenn n = 2 (der Fall m = 2 geht natürlich genauso), gibt es nur zwei Farben und mindestens m + 1 Karten. Ein Symbol x muss also in beiden Farben vorkommen. Spiele nun alle Karten außer x in der einen Farbe, dann beide x-Karten, dann die der anderen Farbe.
Seien nun m, n >= 3. OBdA ist m <= n (sonst vertausche die Rollen von Farben und Symbolen). Von den m*n möglichen Karten fehlen höchstens m + n - 3 < 2n. Es muss also eine Farbe geben, von der höchstens eine Karte aussortiert wurde. Ansonsten würden ja mindestens zwei Karten pro Farbe fehlen, also insgesamt 2n. Sei nun f eine solche Farbe.
Fall 1: Alle m Karten der Farbe f sind vorhanden.
Entferne alle f-Karten und füge eine beliebige fehlende Karte x einer anderen Farbe hinzu (wenn es eine solche gibt). Dann hat man eine Situation mit m Symbolen, n-1 Farben und mindestens (m-1)(n-1)+2 - m + 1 = (m-1)(n-2)+2 vorhandenen Karten. Nach Induktion können diese Karten alle hintereinander abgelegt werden. Wähle eine Abfolge der Karten, mit der dies möglich ist.
Fall 1a: x ist erste oder letzte Karte der Abfolge, oder x wird zwischen zwei Karten mit dem gleichen Symbol gespielt.
Dann kann x aus der Abfolge entfernt werden, die Abfolge bleibt zulässig. Füge am Ende noch die Karten der Farbe f an (erst die mit dem gleichen Symbol wie die bisher letzte Karte, dann die anderen in beliebiger Reihenfolge). Das ergibt eine gültige Abfolge der anfangs gegebenen Karten.
Fall 1b: x wird zwischen zwei Karten mit verschiedenen Symbolen gespielt.
Ordne die Karten der Farbe f so an, dass die erste das gleiche Symbol hat wie die Karte vor x und die letzte das gleiche Symbol wie die Karte nach x. Ersetze x durch diese Abfolge und erhalte wieder eine zulässige Ablagereihenfolge.
Fall 2: Von Farbe f fehlt nur das Symbol s.
Entferne alle f-Karten. Dann hat man mindestens (m-1)(n-1) + 2 - (m-1) = (m-1)(n-2) + 2 Karten in n-1 Farben mit m Symbolen. Nach Induktion können diese Karten zu einer gültigen Ablagefolge angeordnet werden. Wähle eine solche Folge.
Fall 2a: Die erste oder letzte Karte dieser Folge hat nicht das Symbol s.
Dann gibt es eine f-Karte die direkt vor oder direkt nach der Folge ohne f abgelegt werden kann. Füge schließlich die restlichen f-Karten am Anfang bzw. am Ende an und erhalte eine gültige Ablagefolge.
Fall 2b: Die erste und letzte Karte tragen beide das Symbol s.
Dann passen erste und letzte Karte aneinander. Man kann also an einer beliebigen Stelle die Ablagefolge beginnen, bis zum Ende durchspielen und dann am Anfang beginnen, um die restlichen Karten abzulegen. Insbesondere kann man so erreichen, dass die Sequenz mit einem Symbol ungleich s endet. Ansonsten gab es nur s- und f-Karten am Anfang, ohne die Karte (f, s). Das wären maximal m + n - 2 < m+n-2 + (m-2)(n-2) + 1 = (m-1)(n-1) + 2. Nach dieser Umsortierung weiter wie in 2a.