Mathekalender / Archiv /

Ordnung ins Adventschaos

Weihnachtsmann stellt Dienstplan auf

An Schlaf darf der Weihnachtsmann in diesen Tagen nur noch ausnahmsweise denken.
An Schlaf darf der Weihnachtsmann in diesen Tagen nur noch ausnahmsweise denken. (AP)

Beim Weihnachtsmann hat der Endspurt begonnen. In diesem Jahr hat die Vorbereitung seit dem Sommer zwar so gut wie nie geklappt, aber vier Wochen vor Weihnachten bricht trotzdem Hektik aus. Die Wichtel, die wichtigsten Helfer des Weihnachtsmanns, müssen jetzt nach einem optimierten Arbeitsplan eingesetzt werden, sonst droht Weihnachten ohne Geschenke zu bleiben.

Der Weihnachtsmann muss daher seine Helfer bestmöglich einsetzen, um all die Wünsche pünktlich erfüllen zu können. Eine Gruppe von 9 Wichteln soll in Teilgruppen zur Arbeit im Nord-, Ost-,Süd- und Westlager eingeteilt werden. Jede Teilgruppe muss aus mindestens einem Wichtel bestehen.

Aufgabe:


Wie viele mögliche Einteilungen gibt es?
             70
             770
             7770
             77770
             777770
             7777770
             77777770
             777777770
             77777777770
             Es gibt unendlich viele Einteilungen.

Antwort


Zerknirscht müssen wir schon bei der ersten Frage unseres Mathekalenders eine fehlerhafte Lösung eingestehen. Die richtige Antwort ist:

             Es gibt 186480 Einteilungen.

Es tut uns ausgesprochen Leid. Der ausgelobte Preis geht dennoch an Matthias Fischer aus Kiel.

Als Entschuldigung für unseren Fehler und Anerkennung für Ihre zahlreichen Zuschriften ergänzen wir unsere vier Adventsfragen noch um eine zusätzliche Silvesterfrage. Den Preis stiftet unser Redaktionsleiter.

Freuen Sie sich also auf einen zusätzlichen Rätselspaß zum Jahresende. Auch dieser wird um 10:00 Uhr auf der Webseite des Deutschlandfunk-Mathekalenders erscheinen, allerdings am Montag, 31.12.. Über den Jahreswechsel hinweg haben Sie dann bis Neujahr, 8:00 Uhr, Zeit zu knobeln.
Die Redaktion

Und hier die korrekte

Lösung


In unserer unten stehenden Lösung haben wir übersehen, dass die Wichtelgruppen auch den vier Produktionsstätten zugeordnet werden müssen. Es wird zwar korrekt beschrieben, auf wie viele Arten die Wichtel in vier verschiedene Teilgruppen eingeteilt werden können, die jeweils mindestens aus einem Wichtel bestehen. Doch die anschließende Zuordnung zu den Arbeitsstätten fehlt noch.

Die Anzahl der möglichen Zuordnungen bei vier Produktionsstätten ist

         4! = 4 ⋅ 3 ⋅ 2 ⋅ 1 = 24

Beziehungsweise bei k Produktionsstätten

         k! = k ⋅ (k-1) ⋅ ... ⋅ 1.

Unser Endergebnis muss also noch mit 24 multipliziert werden, wodurch sich die Zahl 186480 ergibt.

Die Aufteilung der Wichtel auf die Arbeitsgruppen funktioniert wie bereits beschrieben:


Wir lösen eine verallgemeinerte Form des Rätsels, nämlich den Fall, dass n Wichtel in k Teilgruppen eingeteilt werden sollen. Das machen wir nicht einfach, damit es möglichst kompliziert wird, sondern -- im Gegenteil -- es vereinfacht die nachfolgenden Erklärungen. Die Anzahl der Einteilungen bezeichnen wir mit A(n,k) . Wir suchen also A(9,4) .

Man wähle einen Wichtel aus, den wir im Folgenden Herrn F. nennen. Angenommen es wurde eine Einteilung vorgenommen, dann gibt es zwei Möglichkeiten:

             (i) Herr F. bildet bereits eine Teilgruppe, er muss also alleine arbeiten.
             (ii) Herr F. ist Mitglied einer größeren Teilgruppe, er muss also nicht alleine arbeiten.

In Fall (i) müssen wir das ursprüngliche Problem der Einteilungen für n-1 und k-1 lösen, schließlich ist Herr F. ja bereits eine Teilgruppe. Als nächstes ist also A(n-1,k-1) gesucht.

Im Fall (ii) müssen n-1 Wichtel in k Teilgruppen aufgeteilt werden. Denn wir wissen, dass Herr F. keine eigenständige Teilgruppe bildet. Wir suchen also A(n-1,k) und es gibt damit k ⋅ A(n-1,k) viele Teilgruppen dieser Art. Wir können Herrn F. nämlich zu einer beliebigen der k Teilgruppen hinzufügen, um die komplette Einteilung zu erhalten.

Damit ergibt sich die Formel

             A(n,k) = A(n-1,k-1) + k ⋅ A(n-1,k)

Außerdem kann man sich leicht überlegen, dass für positive ganze Zahlen k und n die Gleichungen A(n,1) = 1 und A(k,k) = 1 gelten. Um unser ursprüngliches Problem zu lösen, müssen wir folgendermaßen rechnen:

         A(9,4)=A(8,3)+4A(8,4)
                   =A(7,2)+3A(7,3)+4(A(7,3)+4A(7,4))
                   =A(7,2)+7A(7,3)+16A(7,4)
                   =A(6,1)+2A(6,2) + 7(A(6,2)+3A(6,3))+16(A(6,3)+4A(6,4))
                   =1+9A(6,2)+37A(6,3)+64A(6,4)
                   =1+9(A(5,1)+2A(5,2))+37(A(5,2)+3A(5,3))+64(A(5,3)+4A(5,4))
                   =1+9+55A(5,2)+175A(5,3)+256A(5,4)
                   =10+55(A(4,1)+2A(4,2))+175(A(4,2)+3A(4,3))+256(A(4,3)+4A(4,4))
                   =10+55+285A(4,2)+781A(4,3)+1024
                   =1089+285(A(3,1)+2A(3,2))+781(A(3,2)+3A(3,3))
                   =1089+285+1351A(3,2)+2343
                   =3717+1351(A(2,1)+2A(2,2))
                   =3717+1351 ⋅ 3
                   =7770

Die Zahlen A(n,k) heißen übrigens Stirling-Zahlen zweiter Art.

Beitrag hören

 
 
Dradio Audio
Kein Audio aktiv
 
 
 
 
 

Mathekalender

Lange Weihnachten

Der Dunkelwald

Das Verteilen der Geschenke verlief für den Weihnachtsmann in diesem Jahr leider sehr unglücklich. Nicht nur, dass viele Kinder mit der Geschenkeauswahl unzufrieden waren und er viele Geschenke umtauschen muss, nein, auch die wichtigste Verbindungsstrecke zurück ist gesperrt. So muss er in diesem Jahr den gefährlichen Umweg durch den Dunkelwald nehmen.

Schleim

Der Weihnachtsmann hat sich die Verantwortung für Giftmüllentsorgung aufschwatzen lassen.

Wir erinnern uns an die Missetaten des Grinchs. Und was hat der Grinch nun wieder angerichtet? Dem gemeinen Kerl ist es doch tatsächlich gelungen, dem Weihnachtsmann die Verantwortung für die Giftmüllentsorgung der Chemiefabrik aufzuhalsen!

Mehr Platz für Rudolph und Co.

Der Weihnachtsmann gönnt auch seinen Rentieren etwas.

Der Platzbedarf moderner Gesellschaften geht auch an den Rentieren des Weihnachtsmanns nicht spurlos vorüber. Rudolph, Voxen und die anderen wollen ein größeres Gehege und endlich hat der Weihnachtsmann eingewilligt. Sparsam wie er ist, will er aber den Zaun des Alten weiterverwenden und nur so viel Baumaterial wie unbedingt nötig hinzukaufen.