Mathematik-Online-Aufgabensammlung: Lösung zur Aufgabe der (letzten) Woche

	[Home] [Lexikon] [Aufgaben] [Tests] [Kurse] [Begleitmaterial] [Hinweise] [Mitwirkende]
	Mathematik-Online-Aufgabensammlung:
	Lösung zur Aufgabe der (letzten) Woche

Aufgabe:

#./interaufg864.tex#Wie viele Möglichkeiten gibt es, die Ziffern

in einem 4x4-Schema anzuordnen, wenn

a): jede Ziffer 4-mal vorkommt,
b): zusätzlich in jeder Zeile alle Ziffern auftreten,
c): darüber hinaus auch in jeder Spalte keine Ziffer doppelt vorkommt?

Die folgenden Beispiele illustrieren die verschiedenen Fälle.

1	1	1	1
2	2	3	3
4	2	2	3
4	4	4	3

1	2	3	4
1	3	4	2
3	2	4	1
3	4	2	1

1	2	3	4
2	1	4	3
3	4	1	2
4	3	2	1

Geben Sie ein Schema an, bei dem zusätzlich zu a) - c) ebenfalls auf den Diagonalen keine gleichen Ziffern stehen.

Antwort:

a) b) c)

Lösung:

a) Ohne Einschränkung können die Positionen der vier Einsen aus 16 Möglichkeiten ausgewählt werden, d. h. es gibt

$\displaystyle \left( \begin{array}{c} 16 \\ 4 \end{array} \right) = \dfrac{16 \cdot 15 \cdot 14 \cdot 13}{4 \cdot 3 \cdot 2 \cdot 1} = 1820 \$ Möglichkeiten $\displaystyle .$

Analog gibt es

$\displaystyle \left( \begin{array}{c} 12 \\ 4 \end{array} \right) = 495 \$ Möglichkeiten $\displaystyle ,$

vier Zweien auf den verbleibenden 12 Positionen,
und dann

$\displaystyle \left( \begin{array}{c} 8 \\ 4 \end{array} \right) = 70 \$ Möglichkeiten $\displaystyle ,$

vier Dreien zu platzieren. Die Positionen der Vieren liegen dann fest.
Die Gesamtzahl der Möglichkeiten ist also

$1820 \cdot 495 \cdot 70 = 63.063.000.$

b) Jede Zeile kann eine beliebige Permutation der vier Ziffern enthalten. Damit gibt es je Zeile

4! = 24 Möglichkeiten,

insgesamt also

Möglichkeiten.

c) Nach Permutation von Zeilen und Spalten des Schemas ( $4! \cdot 3! = 144$ Möglichkeiten) kann man annehmen, dass die Ziffern in der ersten Zeile und Spalte in aufsteigender Reihenfolge stehen:

1	2	3	4
2
3
4

Ausgehend von einer Platzierung der 4 in der zweiten Zeile gibt es dann noch die folgenden vier Möglichkeiten:

1	2	3	4
2	$\vbox{\kern3pt\textcircled{{4}}}$	1	3
3	1	4	2
4	3	2	1

1	2	3	4
2	3	$\vbox{\kern3pt\textcircled{{4}}}$	1
3	4	1	2
4	1	2	3

1	2	3	4
2	1	$\vbox{\kern3pt\textcircled{{4}}}$	3
3	4	1	2
4	3	2	1

1	2	3	4
2	1	$\vbox{\kern3pt\textcircled{{4}}}$	3
3	4	2	1
4	3	1	2

Insgesamt sind es

$144 \cdot 4 = 576$ Möglichkeiten.

Eine mögliche Anordnung ohne Wiederholungen in den Diagonalen ist

1	3	4	2
4	2	1	3
2	4	3	1
3	1	2	4

[Aufgabe der Woche]