Hans Walser, [20190907]

TŸrme

Anregung: P. M., G.

1   Worum geht es?

Kombinatorik. Zahlentheorie

2   Die Turm-Aufgabe

Eine Uraltaufgabe der Kombinatorik: auf wie viele Arten kšnnen acht paarweise feindliche TŸrme so auf einem Schachbrett aufgestellt werden, so dass keiner einen anderen schlagen kann?

Es muss in jeder Spalte und in jeder Zeile genau ein Turm stehen.

Die Abbildungen 1 und 2 zeigen je ein Beispiel. Worin besteht der Unterschied zwischen diesen beiden Beispielen?

Abb.1: Acht TŸrme

Abb. 2: Andere Anordnung

Die TŸrme der Abbildungen 1 und 2 besetzen zwar dieselben Felder im Schachbrett, sind aber intern anders angeordnet (die beiden TŸrme in den ersten beiden Spalten sind vertauscht).

Es gibt daher  Mšglichkeiten, nŠmlich 8! fŸr die Auswahl der Felder und anschlie§end 8! fŸr die Besetzung einer bestimmten Felderkonfiguration mit den einzelnen TŸrmen.

3   Nummerierung

Wir nummerieren die Felder des Schachbrettes von 0 bis 63 gemŠ§ Abbildung 3.

Abb. 3: Nummerierung

Weiter markieren wir die Felder gemŠ§ den Positionen der TŸrme der Abbildungen 1 und 2 (Abb. 4). Es gibt 8! = 40320 Markierungsmšglichkeiten.

Abb. 4: Positionen der TŸrme

Die Summe der markierten Zahlen ist 252.

4   Anderes Beispiel

Die Abbildung 5 zeigt eine andere Positionsbelegung der TŸrme, die Abbildung 6 die zugehšrigen Markierungen im nummerierten Schachbrett.

Abb. 5: Andere Positionsbelegung

Abb. 6: Markierungen

Die Summe der markierten Zahlen ist wiederum 252.

5   Lehrer LŠmpel

a)     Gibt es bei allen 40320 Markierungsmšglichkeiten die Summe 252?

b)    Warum ist das so?

c)     Was Šndert sich, wenn wir die Felder von 1 bis 64 nummerieren?

d)    Wie ist es allgemein mit n TŸrmen in einem n×n-Schachbrett?

e)     Warum sind die Summen immer durch 3 teilbar?

6   Bearbeitung der Fragen

Wir nummerieren die Felder mit dem Positionssystem auf der Basis 8 (Abb. 7).

Abb. 7: Positionssystem auf der Basis 8

In jeder Spalte haben wir jetzt immer dieselbe Einerziffer, und zwar der Reihe nach die Ziffern 0, 1, ... , 7. In jeder Zeile haben wir dieselbe Achterziffer, und zwar der Reihe nach die Ziffern 0, 1, ... , 7.

In der Abbildung 8 sind zusŠtzlich die Markierungen eingetragen, welche den Turmpositionen der Abbildungen 1, 2 und 4 entsprechen.

Abb. 8: Markierungen

Wir haben in jeder Spalte und in jeder Zeile genau einen Turm. Daher kommen in den markierten Feldern insgesamt genau die Einerziffern 0, 1, ... , 7 und ebenso die Achterziffern 0, 1, ... , 7 vor. FŸr die Gesamtsumme S hei§t das:

 

                 (1)

 

 

 

Wenn wir von 1 bis 64 nummerieren, wird jede Zahl um 1 erhšht. Die Summe erhšht sich daher um 8. Wir erhalten die Summe 260.

In einem n×n-Schachbrett gilt entsprechend bei der Nummerierung von 0 bis :

 

 

                                                                     (2)

 

Da die Summe S bis auf den Faktor  das Produkt dreier aufeinanderfolgender natŸrlicher Zahlen ist, ist sie durch 3 teilbar.

Der Quotient ist offenbar der Binomialkoeffizient .

Die Tabelle 1 zeigt die ersten Werte.

 

n

S

0

0

0

0

1

0

0

0

2

3

1

1

3

12

4

4

4

30

10

10

5

60

20

20

6

105

35

35

7

168

56

56

8

252

84

84

9

360

120

120

10

495

165

165

Tab. 1: Werte

Damit sind die Fragen des Lehrers LŠmpel beantwortet. Das mit den Binomialkoeffizienten hat er offenbar nicht gewusst.