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

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

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

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