Das Invarianzprinzip

Auf einem Tisch liegen fünf Münzen im Kreis angeordnet. Am Anfang zeigen alle Münzen Kopf. Du darfst jetzt beliebig oft zwei benachbarte Münzen umdrehen. Kannst du erreichen, dass alle Münzen Zahl zeigen?

In diesem Artikel werden wir uns ein paar kombinatorische Aufgaben anschauen, die sich alle elegant mit einer Invariante lösen lassen. Eine Invariante ist eine Eigenschaft oder ein Zustand, der sich nicht ändert. Die Idee ist dann eine solche Eigenschaft zu finden, sodass sie in Start- und Zielstellung verschieden ist. Ich empfehle, die Aufgaben jeweils zunächst selbst zu probieren.

Bei der Eingangsaufgabe kann man ein bisschen ausprobieren, was für Positionen denn so möglich sind. Es fällt auf, dass man nur Stellungen erreicht, bei denen keine, zwei oder vier Münzen Zahl zeigen. Es scheint nicht möglich zu sein, alle Münzen umzudrehen. Man könnte vermuten, dass die Parität der Anzahl Münzen, die Zahl zeigen, eine Invariante ist. Es ist also zu zeigen, dass sich bei jedem Schritt diese Parität nicht ändert. Wenn man nur eine Münze umdreht, ändert sich die Parität genau. Entweder nimmt die Anzahl der Münzen mit Zahl um 1 ab oder nimmt um 1 zu. Wenn man zwei Münzen umdreht, ändert sich die Parität also zweimal und bleibt somit gleich. Dass die Münzen benachbart sein müssen, braucht man also überhaupt nicht.

Am Anfang ist die Parität der Münzen mit Zahl gerade, in der Schlussstellung soll sie ungerade sein, das ist nicht möglich, also kannst du diese Position nicht erreichen.

Eine weitere Aufgabe

In den unteren vier Reihen eines Schachbretts steht in jedem Feld ein Bauer. Du darfst nun beliebig oftzwei Bauern aus der gleichen Reihe entfernen und dafür einen Bauern in der Reihe darüber dazustellen. Kannst du dabei einen Bauern in die oberste Reihe stellen?

In jedem Zug werden zwei Bauern durch einen ersetzt. Dafür steht dieser dann in einer größeren Reihe. Wir geben den Bauern Wertigkeiten in Abhängigkeit von ihrer Reihe. Dabei soll die Summe dieser Wertigkeiten genau erhalten bleiben. Das heißt, dass die Bauern in einer Reihe höher doppelt so viel Wert sind. Die Bauern aus der unteren Reihe bewerten wir mit 1. Damit haben die Bauern der zweiten Reihe Wertigkeit 2. Die nächsten Wertigkeiten sind dann 4, 8, 16, 32, 64 und ein Bauer in der obersten Reihe hat Wertigkeit 128.

Die Summe der Wertigkeiten aller Bauern ist eine Invariante, schließlich sind die Bewertungen genauso konstruiert worden. Wir wollen am Ende einen Bauern in der obersten Reihe stehen haben, also haben wir dann mindestens eine Summe von 128. Am Anfang ist die Summe jedoch nur 8\cdot (1+2+4+8)=8 \cdot 15 =120. Also ist es nicht möglich.

Färbungen

Die folgende Aufgabe ist ein Standardbeispiel, vielleicht ist es dir also schon einmal begegnet.

Bei einem Schachbrett fehlen die linke untere und rechte obere Ecke. Kann man dieses Brett vollständig mit passenden Dominosteinen abdecken? Die Dominosteine dürfen sich nicht überlappen und sie dürfen nicht über den Rand des Brettes herausragen.

Es scheint zunächst so, als sollte das möglich sein, weil ein Dominostein doch sehr klein ist und man somit sehr viele Möglichkeiten hat. Egal wie man es aber versucht, am Ende würde man gerne einen Dominsostein zerschneiden. Doch warum geht das nicht?

Praktischerweise kommt ein Schachbrett gleich mit einer Färbung in schwarze und weiße Felder. Die linke untere und rechte obere Ecke haben die gleiche Farbe, das sind beides schwarze Felder. Es bleiben also 30 schwarze und 32 weiße Felder. Ein Dominstein deckt aber immer genau benachbarte Felder ab und diese haben verschiedene Farben. Also kann man dieses Schachbrett nicht mit Dominosteinen abdecken.

Was haben Färbungen mit Invarianten zu tun?

Wir können die Differenz der Anzahl weißer Felder und der Anzahl schwarzer Felder betrachten. Das ist eine Invariante, die sich beim Legen eines Dominosteins nicht verändert. Am Anfang ist sie 2 und am Ende soll sie 0 sein.

Manchmal ist die Färbung auch nicht direkt gegeben, wie zum Beispiel in der folgenden recht ähnlichen Aufgabe.

Kann man ein 10\times 10-Brett mit 1\times4-Steinen vollständig abdecken? Auch hier dürfen sich die Steine nicht überlappen und auch nicht über den Rand hinausragen.

Wenn wir hier die Felder abwechselnd weiß und schwarz färben, gibt es genau 50 schwarze und 50 weiße Felder. Jeder Stein überdeckt dann genau zwei weiße und zwei schwarze Felder. Diese Färbung hilft also nicht weiter. Schließlich heißt es ja nicht, dass nur weil diese Färbung kein Gegenargument liefert, es tatsächlich möglich ist. Etwas rumprobieren führt aber zu dieser Vermutung, wir müssen also eine bessere Färbung finden. Wir könnten jeweils komplette 2\times2-Felder abwechseln schwarz und weiß färben (male dir das doch mal auf). Da wir dann ein im Prinzip ein 5\times 5-Feld färben, ist die Anzahl der schwarzen und Anzahl der weißen Felder dann auch verschieden. Wenn wir in der linken unteren Ecke mit schwarz anfangen, erhalten wir 13 schwarze 2\times2-Felder und 12 weiße 2\times2-Felder. Es sind also 52 Felder schwarz gefärbt und 48 Felder weiß gefärbt. Jeder Stein überdeckt aber genau zwei schwarze und zwei weiße Felder. Damit zeigt diese Färbung tatsächlich, dass es nicht möglich ist.

Im nächsten Artikel beschäftigen wir uns noch einmal mit Kopfrechnen, und zwar mit Quadratwurzeln.