Sechzehn Nullen zur Auswahl

Die folgende Aufgabe lehnt sich an ein Problem an, das ein russischer Klassiker der mathematisch-naturwissenschaftlichen Pädagogik, J.I. Perelman, in seinem 1913 erschienenen Bestseller "Unterhaltsame Aufgaben und Versuche" aufgegriffen hat.

Die Plätze einer 4x4-Matrix seien mit lauter Nullen besetzt:

0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

Es sind acht der sechzehn Nullen durch eine 1 zu ersetzen, so dass in jeder Zeile und in jeder Spalte genau zwei Nullen und zwei Einsen stehen.
Geben Sie ein Beispiel dazu an.
Wie viele Möglichkeiten für solche Ersetzungen gibt es?

Da nicht ausgeschlossen ist, dass zwei der Zeilen gleich sein können, ist ein Beispiel einer Ersetzung das folgende (*)

1 1 0 0
1 1 0 0
0 0 1 1
0 0 1 1

Wie viele Ersetzungen gibt es?

Die Zeilen können die folgenden 6 Formen haben (**) :

1100 1010 1001 0110 0101 0011

Genau zwei aus den ersten drei der Zeilen (**) müssen in jeder Lösungsmatrix vorkommen, denn nur so ist gewährleistet, dass in der ersten Spalte genau zwei Einsen stehen.

1) Falls die aus den drei ersten Zeilen ausgewählten beiden Zeilen gleich sind, gibt es bis auf Vertauschung der Zeilen die folgenden drei Möglichkeiten einer Lösungsmatrix: Neben der in (*) aufgeführten noch die beiden ( wir lassen die Tabellenhäuschen weg):

1010 1001
1010 und 1001
0101 0110
0101 0110

Zu jeder dieser drei Matrizen gibt es 4!/(2!2!) = 6 Möglichkeiten, die Zeilen zu vertauschen, so dass man auf 3•6 = 18 Lösungsmatrizen im Fall 1) kommt.

2) Zwei verschiedene Zeilen aus den ersten drei in (**) werden ausgewählt, wozu es drei Möglichkeiten gibt. Bis auf Zeilenvertauschungen führt das zu den drei Lösungsmatrizen

1100 1100 1010
1010 1001 1001
0101 0011 0110
0011 0110 0101

Zu jeder Matrix gibt es 4! = 24 Möglichkeiten der Zeilenvertauschung, und so erhält man im Fall 2) 3•24 = 72 Lösungsmatrizen.

Insgesamt gibt es 18 + 72 = 90 Lösungsmatrizen.

Man kann die Aufgabe auch wie folgt lösen. Die sechs Zeilen in (**) stellen im Dualsystem die Zahlen 12, 10,9, 6, 5, 3 dar. Fasst man die Zeilen einer Lösungsmatrix als eine Zahl im Dualsystem auf, so ist die Summe der Zeilen jeder Lösungsmatrix gleich ( dual) 11110, das ist gleich 30 ( davon kann man sich überzeugen, wenn man bedenkt, dass in jeder Spalte genau zwei Einsen und zwei Nullen vorkommen).

Die Aufgabe kann demnach auch wie folgt formuliert werden. Wie viele Möglichkeiten gibt es, aus den sechs Zahlen 12, 10, 9, 6, 5, 3 vier so auszuwählen, dass sich die Summe 30 ergibt? Dabei kann eine Zahl auch zweimal, aber nicht dreimal vorkommen.

Zunächst ist klar, dass wegen 6+5+3 = 14 = 30 – 16 mindestens zwei, wegen 12+10+9 = 31 höchstens zwei, mithin genau zwei aus den drei Zahlen 12, 10, 9 in der Summe vorkommen müssen.

1) Zwei gleiche Zahlen aus 12, 10, 9 . Das ergibt bis auf Reihenfolge der Summanden die drei Möglichkeiten 12 + 12+ 3 + 3, 10 + 10 + 5 + 5 , 9 + 9 + 6 + 6 . Berücksichtigt man die Reihenfolge, so ergeben sich zu 1) 3•4!/(2!2!) = 18 Möglichkeiten.

2) Zwei ungleiche Zahlen aus 12,10,9 . Das ergibt bis auf Reihenfolge der Summanden die drei Möglichkeiten 12 + 10 + 5 + 3 , 12 + 9 + 6 + 3, 10 + 9 + 6 + 5 . Berücksichtigt man die Reihenfolge, so ergeben sich zu 2) 3•4! = 72 Möglichkeiten.

Insgesamt ergeben sich 18 + 82 = 90 Lösungen.

Zum Schluss noch eine Episode. In dem erwähnten Buch von Perelman wird eine 6x6- Matrix vorgestellt, deren 36 Plätze sämtlich mit Nullen gefüllt sind. Es sind 12 Nullen so zu streichen, dass in jeder Zeile und in jeder Spalte die gleiche Anzahl nicht gestrichener Nullen verbleibt. Zu diesem Problem gibt es kolossal viele Lösungen. In dem Buch ist eine aufgeführt. Nun gibt es in der russischen Sprache weder einen bestimmten noch einen unbestimmten Artikel, und in der deutschen Übersetzung ist zu lesen : „Die Verteilung der gestrichenen Nullen ist....“ ( statt: „Eine Verteilung der gestrichenen Nullen ist...“). Da mag der Leser, dem eine andere Verteilung aus der Menge der kolossal vielen Lösungen eingefallen ist, ins Grübeln kommen...