Dienstag, 19. März 2024


Ordnung ins Adventschaos

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.

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