Kombinatorik

Eine Zahl darf nicht mit 0 beginnen – sonst wäre 0123 nur die dreistellige Zahl 123. Für die erste Stelle kommen also nur 1, 2, 3 in Frage: 3 Möglichkeiten. Die übrigen drei Ziffern, darunter jetzt auch die 0, verteilen sich beliebig auf die drei restlichen Stellen: $3!=6$ Möglichkeiten.

Ohne Einschränkung gibt es $4!=24$ Anordnungen der vier Ziffern. Unbrauchbar sind die, die mit 0 beginnen. Bei ihnen werden die übrigen drei Ziffern beliebig angeordnet, das sind $3!=6$ Stück. Wir ziehen sie ab:

Diese Methode – alle zählen und die unbrauchbaren abziehen – heißt Zählen über das Komplement.

Eine Zahl ist gerade, wenn ihre letzte Ziffer gerade ist. Die strengste Bedingung betrifft also die letzte Stelle – mit ihr fangen wir an. Dort kann 2 oder 4 stehen: 2 Möglichkeiten. Die drei übrigen Ziffern verteilen sich beliebig auf die ersten drei Stellen: $3!=6$ Möglichkeiten.

Jetzt gibt es zwei Bedingungen: Die letzte Ziffer muss gerade sein (0, 2 oder 4), und die erste Ziffer darf nicht 0 sein.

Die beiden Bedingungen hängen voneinander ab: Steht die 0 hinten, kann sie vorne gar nicht mehr stören. Steht sie nicht hinten, muss man vorne auf sie aufpassen. Deshalb unterscheiden wir Fälle nach der letzten Ziffer.

Fall 1: Die letzte Ziffer ist 0. Die Ziffern 1, 2, 3, 4 verteilen sich beliebig auf die ersten vier Stellen. Keine davon ist 0, es gibt also keine weitere Einschränkung: $4!=24$ Zahlen.

Fall 2: Die letzte Ziffer ist 2. Übrig sind 0, 1, 3, 4. An der ersten Stelle darf keine 0 stehen, dort gibt es also 3 Möglichkeiten. Die restlichen drei Ziffern verteilen sich beliebig: $3!=6$. Zusammen $3\cdot6=18$ Zahlen.

Fall 3: Die letzte Ziffer ist 4. Genau wie Fall 2: 18 Zahlen.

Kontrolle über das Komplement: Anordnungen mit gerader letzter Ziffer gibt es $3\cdot4!=72$. Davon beginnen mit 0 diejenigen, die auf 2 oder 4 enden, das sind $2\cdot3!=12$. Es bleiben $72-12=60$.

Eine Zahl ist durch 5 teilbar, wenn sie auf 0 oder 5 endet. Außerdem darf sie nicht mit 0 beginnen. Die Lage ist dieselbe wie in Aufgabe 11, also unterscheiden wir wieder Fälle nach der letzten Ziffer.

Fall 1: Die letzte Ziffer ist 0. Die Ziffern 1 bis 5 verteilen sich beliebig auf die ersten fünf Stellen: $5!=120$ Zahlen.

Fall 2: Die letzte Ziffer ist 5. Übrig sind 0, 1, 2, 3, 4. Für die erste Stelle gibt es 4 Möglichkeiten (nicht 0), die restlichen vier Ziffern verteilen sich beliebig: $4!=24$. Zusammen $4\cdot24=96$ Zahlen.

Die erste Stelle darf nicht 0 sein, dort steht also 1 oder 2: 2 Möglichkeiten.

Für die restlichen drei Stellen bleiben zwei Nullen und eine weitere Ziffer übrig. Eine solche Anordnung steht fest, sobald man weiß, wo die Ziffer steht, die keine Null ist. Dafür gibt es 3 Möglichkeiten.

Mit gefärbten Nullen gäbe es $4!=24$ Anordnungen, ohne Farben also $24:2=12$.

Davon streichen wir die, die mit einer 0 beginnen. Hinter dieser 0 stehen die restlichen Ziffern 0, 1, 2. Sie sind alle verschieden, also gibt es $3!=6$ solche Anordnungen. Achtung: Hier darf man nicht noch einmal durch 2 teilen, denn im Rest gibt es nur noch eine Null.

Kontrolle durch Aufschreiben: 1002, 1020, 1200, 2001, 2010, 2100.

Wir kleben 2 und 3 zu einem Block zusammen und behandeln ihn wie eine einzige Ziffer. Zu ordnen sind dann vier Teile: der Block, 1, 4 und 5. Dafür gibt es $4!=24$ Möglichkeiten. Innerhalb des Blocks kann 23 oder 32 stehen: 2 Möglichkeiten.

Zwei benachbarte Plätze sind (1,2), (2,3), (3,4) oder (4,5): 4 Möglichkeiten. Auf ihnen stehen 2 und 3 in einer der 2 Reihenfolgen. Die übrigen drei Ziffern verteilen sich auf die übrigen drei Plätze: $3!=6$ Möglichkeiten.

Von allen 120 Zahlen haben nach Aufgabe 14 genau 48 die Ziffern 2 und 3 nebeneinander. Alle anderen erfüllen die Bedingung:

Wir stellen zuerst die Ziffern 1, 4, 5 auf: $3!=6$ Möglichkeiten. Zwischen ihnen und an den Rändern entstehen vier Lücken:

Setzen wir 2 und 3 in zwei verschiedene Lücken, können sie nicht nebeneinander landen. Umgekehrt entsteht jede passende Zahl auf genau diese Weise. Für die 2 gibt es 4 Lücken, für die 3 danach noch 3.

Zu jeder Zahl bilden wir eine Partnerzahl, indem wir die Ziffern 2 und 3 vertauschen. Aus 21534 wird zum Beispiel 31524. Von jedem solchen Paar erfüllt genau eine Zahl die Bedingung – die, in der die 2 links steht. Die 120 Zahlen zerfallen in 60 Paare, also gibt es 60 passende Zahlen.

Das ist die Idee aus Teil A, diesmal rückwärts. Wir ersetzen 2 und 3 durch zwei gleiche Zeichen X, X. Wie in Aufgabe 3 gibt es dann $120:2=60$ Anordnungen von X, X, 1, 4, 5. In jeder davon setzen wir für das linke X die 2 und für das rechte X die 3 ein. So entsteht jede passende Zahl genau einmal.

Die Plätze von 2 und 3 müssen genau zwei auseinanderliegen. Möglich sind die Platzpaare (1,3), (2,4) und (3,5): 3 Möglichkeiten. Auf einem solchen Paar können 2 und 3 in 2 Reihenfolgen stehen. Die übrigen drei Ziffern verteilen sich auf die übrigen drei Plätze: $3!=6$ Möglichkeiten.

Probe: Genauso findet man: Bei 0 Ziffern dazwischen gibt es $4\cdot2\cdot6=48$ Zahlen (Aufgabe 14), bei 2 Ziffern dazwischen $2\cdot2\cdot6=24$, bei 3 Ziffern dazwischen $1\cdot2\cdot6=12$. Jede der 120 Zahlen fällt in genau einen dieser Fälle – und tatsächlich ist $48+36+24+12=120$.

Wir kleben 1, 2, 3 zu einem Block. Zu ordnen sind dann drei Teile: der Block, 4 und 5. Dafür gibt es $3!=6$ Möglichkeiten. Innerhalb des Blocks können 1, 2, 3 in $3!=6$ Reihenfolgen stehen.

Die ungeraden Ziffern sind 1, 3, 5, die geraden 2 und 4. Wir verwenden die Lückenmethode aus Aufgabe 15.

Zuerst stellen wir die geraden Ziffern auf: 2 4 oder 4 2, also 2 Möglichkeiten. Es entstehen drei Lücken:

Die drei ungeraden Ziffern müssen in drei verschiedene Lücken. Es gibt aber nur drei Lücken – also bekommt jede Lücke genau eine ungerade Ziffer. Hier gibt es nichts zu wählen. Wählen kann man nur, welche ungerade Ziffer in welche Lücke kommt: $3!=6$ Möglichkeiten.

Nebenbei sieht man: Die ungeraden Ziffern stehen in jeder solchen Zahl auf den Plätzen 1, 3 und 5.

Wir teilen die 120 Zahlen in Gruppen ein: In eine Gruppe kommen alle Zahlen, bei denen 1 und 5 auf denselben Plätzen stehen. Die Ziffern 2, 3, 4 belegen dann in jeder Gruppe dieselben drei Plätze, nur in verschiedener Reihenfolge. Jede Gruppe enthält deshalb $3!=6$ Zahlen, und genau eine davon hat die Reihenfolge 2, 3, 4 von links nach rechts.

Mit der Färbe-Idee gesagt: Wir ersetzen 2, 3, 4 durch drei gleiche Zeichen X, X, X und rechnen genau wie in Aufgabe 5 (A, A, A, B, C). Dass beide Aufgaben dieselbe Antwort haben, ist also kein Zufall.

Wir verbinden das Kleben aus Aufgabe 14 mit dem Komplement aus Aufgabe 9.

Zuerst kleben wir 2 und 3 zu einem Block. Mit den Teilen Block, 0, 1, 4 gibt es $4!=24$ Anordnungen, mit den 2 Reihenfolgen im Block also 48. Dabei haben wir die Null noch nicht beachtet.

Jetzt ziehen wir die Anordnungen ab, die mit 0 beginnen. Steht die 0 vorne, sind Block, 1 und 4 auf die übrigen Plätze zu verteilen: $3!=6$ Möglichkeiten, mal 2 Reihenfolgen im Block, also 12.

Zuerst nummerieren wir die Stühle von 1 bis 5 und unterscheiden alle Sitzordnungen. Dann gibt es $5!=120$ Möglichkeiten.

Nun drehen wir den Tisch um einen, zwei, drei oder vier Plätze. Zusammen mit der ursprünglichen Ordnung entstehen so 5 nummerierte Sitzordnungen, die verschieden aussehen, aber als gleich gelten. Die 120 Sitzordnungen zerfallen also in Gruppen zu je 5:

Das ist dieselbe Idee wie beim Entfärben in Teil A: Dort haben wir Anordnungen zusammengefasst, die sich nur in den Farben unterscheiden, hier solche, die sich nur durch eine Drehung unterscheiden.

Weil Drehungen keine Rolle spielen, darf sich eine bestimmte Person irgendwohin setzen – ihr Platz ist der Bezugspunkt. Die anderen vier Personen verteilen sich dann, vom Bezugspunkt aus im Uhrzeigersinn gesehen, auf die vier übrigen Plätze: $4!=24$ Möglichkeiten.

Erste Beobachtung: Die 0 kann nicht vorkommen. Sie ist die kleinste Ziffer und müsste deshalb ganz vorne stehen – aber eine Zahl darf nicht mit 0 beginnen. Alle Ziffern stammen also aus 1 bis 9, und sie sind alle verschieden.

Zweite Beobachtung: Wählt man fünf verschiedene Ziffern aus 1 bis 9 aus, gibt es genau eine Möglichkeit, sie aufsteigend anzuordnen. Die Auswahl {7, 2, 9, 4, 5} ergibt zum Beispiel nur die Zahl 24579. Wir müssen also nur zählen, wie viele Auswahlen von fünf Ziffern es gibt.

Dazu zählen wir zuerst mit Reihenfolge: Für die erste gewählte Ziffer gibt es 9 Möglichkeiten, für die zweite 8 und so weiter:

Dabei kommt jede Auswahl in allen $5!=120$ möglichen Reihenfolgen vor, aber nur eine davon ist aufsteigend. Wie in Aufgabe 20 teilen wir:

Stell dir vor, wir schreiben alle 120 Zahlen untereinander und addieren spaltenweise.

Betrachten wir die Einerstelle. Wie oft steht dort zum Beispiel die Ziffer 1? Ist die 1 hinten festgelegt, können die anderen vier Ziffern beliebig davorstehen: $4!=24$-mal. Dasselbe gilt für jede andere Ziffer. Die Einerspalte ergibt also:

Für die Zehner, Hunderter, Tausender und Zehntausender gilt genau dasselbe: Jede Spalte hat die Ziffernsumme 360, nur mit einem anderen Stellenwert. Die Gesamtsumme ist deshalb:

Zu jeder Zahl bilden wir eine Partnerzahl, indem wir jede Ziffer $d$ durch $6-d$ ersetzen: Aus 1 wird 5, aus 2 wird 4, die 3 bleibt 3, aus 4 wird 2, aus 5 wird 1. Aus 13254 wird zum Beispiel 53412.

Die Partnerzahl ist wieder eine der 120 Zahlen. Sie ist auch nie gleich der Ausgangszahl – dafür müsste jede Ziffer gleich 3 sein. Die 120 Zahlen zerfallen also in 60 Paare.

In jedem Paar ergänzen sich die Ziffern an jeder Stelle zu 6. Die Summe eines Paares ist deshalb immer 66 666, zum Beispiel $13\,254+53\,412=66\,666$.