Beim Verteilen der Geschenke hat der Weihnachtsmann versehentlich einige Pakete fallen lassen, die jetzt am Wegrand seiner Route liegen. Natürlich hat er ein paar zusätzliche Geschenke als Reserve dabei, muss aber trotzdem am Ende seiner Reise feststellen, dass das letzte Geschenk nicht für das vorgesehene Kind geeignet ist. Also ruft er einen seiner Wichtel auf dem Handy an und befiehlt ihm, sich von der Fabrik aus auf den Weg zu machen und ihm ein passendes Geschenk zu bringen. Dazu soll der Wichtel die gesamte Route des Weihnachtsmannes ablaufen, wo die verlorenen Pakete liegen. Um herauszufinden, welches der optisch nicht zu unterscheidenden Päckchen das richtige ist, hat ihm der Weihnachtsmann noch ein paar Infos gegeben:
- Insgesamt habe ich mehr Geschenke mit einem passenden Inhalt fallen gelassen, als welche, die ungeeignet sind.
- Alle geeigneten Geschenke wiegen gleich viel, alle anderen haben ein davon abweichendes Gewicht.
- Ich habe nie mehrere Geschenke am selben Ort verloren.
In der Eile kann der Wichtel nur eine Balkenwaage finden, bevor er sich auf den Weg macht. Die Pakete sind im Vergleich zum Wichtel so groß, dass dieser außer der Waage immer nur ein einziges Geschenk mitnehmen kann.
Da es schon fast Mitternacht ist, bleibt keine Zeit, um ein Stück des Weges rückwärts zu gehen oder gar ein Päckchen zu öffnen und hinein zu schauen.
Fieberhaft versucht der Wichtel sich trotz der Umstände eine Strategie zu überlegen, um am Ende auf jeden Fall ein geeignetes Geschenk in der Hand zu halten, wenn er beim Weihnachtsmann ankommt.
Hier noch einige Punkte zur Klarstellung:
- Ungeeignete Geschenke können schwerer oder leichter sein als geeignete.
- Mehrere ungeeignete Geschenke können das gleiche Gewicht haben.
- Der Wichtel kennt die Anzahl der Pakete, die der Weihnachtsmann insgesamt verloren hat, nicht.
- Das einzige Hilfsmittel des Wichtels ist die Balkenwaage, mit der er das Gewicht von 2 Paketen vergleichen kann (keine anderweitigen Gewichte).
- Der Wichtel kann die Route zu keinem Zeitpunkt soweit überblicken, um zu erkennen, wie viele Pakete noch auf der Strecke liegen bzw. wie weit der Weg noch ist.
- Kein vom Weihnachtsmann verlorenes Geschenk wurde vom Kehrdienst, einem spielenden Kind o.Ä. entdeckt oder gar mitgenommen.
- Selbstverständlich kann der Wichtel nicht einfach ein geeignetes Geschenk aus der Fabrik mitnehmen, sondern muss sich für eins der verlorenen entscheiden.
- Übermenschliche Fähigkeiten des Wichtels oder andere Tricks sind natürlich ebenso nicht Teil der Lösung (;
Ist es dem Wichtel unter diesen Umständen mit einer geeigneten Taktik möglich, dem Weihnachtsmann auf jeden Fall ein passendes Päckchen zu überreichen?
Wenn ja, gib die Vorgehensweise des Wichtels stichpunktartig (ohne Begründung!) an. Formuliere deine Antwort dann so:
"JA!
- Stichpunkt 1
- Stichpunkt 2
- Stichpunkt 3"
Wenn nein, gib eine kurze Begründung an (maximal 5 Sätze!). Formuliere deine Antwort dann so:
"NEIN!
Der Wichtel hat keine Chance, sich sicher zu sein, am Ende ein passendes Geschenk in den Händen zu haben, weil....."
Falls es noch Fragen gibt, stellt diese bitte wie gewohnt im Forum (:
Ansonsten von meiner Seite ein frohes Fest und einen guten Rutsch!
| Lösung |
JA! - Der Wichtel nimmt (beginnend mit dem ersten) immer ein Geschenk mit und vergleicht dessen Gewicht mit dem des nächsten. - Dabei merkt er sich jedes mal den Überschuss Ü an Paketen mit gleichem Gewicht (wie das erste Päckchen) im Vergleich zu Paketen mit einem davon abweichenden Gewicht. Zu Beginn ist der Überschuss also bereits Ü = 1. Ist das zweite Paket gleich schwer, ist der Überschuss jetzt Ü = 2. Ist es leichter oder schwerer, ist der Überschuss Ü = 0. - Solange der Überschuss größer als Null ist, behält der Wichtel das Geschenk und geht damit zum nächsten. Ist der Überschuss irgendwann gleich Null, lässt er beide Pakete am Wegrand liegen und geht weiter, bis er das nächste findet. Dann beginnt er die gleiche Strategie von vorne. Begründung (nicht verlangt):
Ist der Überschuss von Anfang bis Ende stets größer als Null (Ü > 0), hat der Wichtel mit Sicherheit ein passendes Geschenk dabei.
Wird der Überschuss jedoch im Laufe der Strecke mindestens einmal gleich Null (Ü = 0), gibt es jedes mal genau zwei Möglichkeiten:
1. Möglichkeit:
Unter den bisher gefundenen Geschenken war die Hälfte unpassend, während ansonsten alle anderen entweder ebenfalls ungeeignet waren, jedoch ein anderes Gewicht hatten, oder sogar passend waren. In diesem Fall sind unter den verbleibenden Geschenken logischerweise immer noch mehr geeignete als ungeeignete, da weniger als die Hälfte der bisher gewogenen Päckchen geeignet waren. Das impliziert auch, dass auf jeden Fall noch mindestens zwei (geeignete) Päckchen am Wegrand liegen müssen. Die Problemstellung ändert sich für die restliche Wegstrecke also nicht.
2. Möglichkeit: Der Wichtel hat bisher genau so viele unpassende wie passende Geschenke gefunden. Damit die Bedingung, dass insgesamt mehr geeignete als ungeeignete Geschenke verloren wurden, erfüllt ist, muss jetzt noch mindestens ein geeignetes am Wegrand liegen, auf jeden Fall aber mehr geeignete als ungeeignete. Die Problemstellung ändert sich also auch hier nicht - jetzt jedoch auf eine kleinere Anzahl von Paketen beschränkt.
Beide Möglichkeiten enden damit, dass der Wichtel mit Überschuss Ü >= 1 beim Weihnachtsmann ankommt und somit auf jeden Fall ein geeignetes Paket gefunden hat.
Ich danke euch allen für's Miträtseln, wünsche frohe Weihnachten und einen guten Rutsch ins neue Jahr!
Lösung ausblenden |
