Rotkäppchen und der Apfelweg

[Otmar]

Hallo Kolabord,

Mehr ->

hab gerade wenig Zeit, aber eine kurze Frage hätte ich noch zu der Anzahl der gleichschweren Äpfel. Zählt da der Apfel im Korb mit rein? Und wenn gewechselt wird, hat Rotkäppchen ja einen Apfel. Ist gleich nach dem Wechsel die Anzahl der gleichschweren Äpfel 1.

Lg. Otmar

[Phoenix]

Mehr ->

Ich bleibe bei meiner Loesung, nur das jetzt der Apfel im Korb zur "gleich" Summe hinzuzaehlt. So ist sie fast so wie die von Kolaboard, nur dass ich die Informationen des Vorgaengerapfels beruecksichtige (obwohl, ich weiss gar nicht, ob das ueberhaupt noetig ist). Zu der Nachfrage von Otmar denke ich, dass der aktuelle Apfel nicht dazuzaehlen soll, deswegen auch erst der Wechsel ab einer Differenz von zwei. Im Endeffekt ist es egal, ob der aktuelle Apfel in der Summe oder der Grenze zum Wechsel steckt. Anderfalls waere Kolaboards Loesung naemlich falsch: Wenn am Anfang ein schlechter Aepfel kommen und danach zwei gute, haette die Oma den Schlechten.

[Otmar]

@Phoenix

Mehr ->

Ich bleibe bei meiner Loesung, nur das jetzt der Apfel im Korb zur "gleich" Summe hinzuzaehlt.

Das sieht dann immer noch nicht gut aus. Angenommen es gibt 2 verschiedene Gewichte S und L und es liegen

L L S S S S L

am Wegrand, dann erhält die Oma bei Anwendung deiner modifizierten Methode, den letzten L Apfel, der offenbar schlecht ist.

nur dass ich die Informationen des Vorgaengerapfels beruecksichtige (obwohl, ich weiss gar nicht, ob das ueberhaupt noetig ist).

Ich glaube, dass diese Vorgängerinformation nicht nur unnötig ist, sondern die sonst richtige Lösungsidee kaputt macht.

@Kolabord

Mehr ->

Zu der Nachfrage von Otmar denke ich, dass der aktuelle Apfel nicht dazuzaehlen soll

Das denke ich inzwischen auch, und dann ist die Lösung völlig

RICHTIG

Denn, Kolabords Lösung ist mit den gleichen Überlegungen zu begründen, wie die für das Problem bekannte Standardlösung, die ich kurz vorstellen möchte:

Mehr ->

Rotkäppchen nimmt den ersten Apfel und behält diesen Apfel, solange sein Gewicht das am meisten vorkommende ist. Dazu merkt sich Rotkäppchen den Überschuss an zum ersten Apfel gleichgewichtigen Äpfeln gegenüber Äpfeln mit anderem Gewicht. Der Überschuss ist beim ersten Apfel 1 und wird nach dem Wiegen des ersten Apfels mit jedem der folgenden Äpfel am Wegrand um eins erhöht, wenn Gleichgewicht besteht und um eins verringert, bei Ungleichgewicht. Sobald der Überschuss 0 ist, geht Rotkäppchen ohne Apfel weiter und beginnt das Spiel beim nächsten Apfel den sie finden wird, von vorn.

Zur Begründung betrachten wir, was passiert, wenn der Überschuss 0 wird:

Angenommen es gibt insgesamt N Äpfel, davon G gute und N - G schlechte also G > N - G. Bei Überschuss 0 hat Rotkäppchen von den N Äpfeln bereits 2*M Äpfel gefunden, wobei keines der vorkommenden Gewichte öfter als M mal vorkam. Es verbleiben N1 = N-2 M Äpfel, wobei noch G1 >= G-M gute Äpfel unter den N1 Äpfeln sein müssen.
Daraus erhalten wir G1 > N1 - G1. Also hat Rotkäppchen nach Überschuss 0 mit den restlichen N1 Äpfeln das gleiche Problem, nur mit 2 M Äpfeln weniger zu lösen, wie beim Ausgangsproblem mit den N Äpfeln. Wegen 2 G1 > N1 ist G1 noch größer als 0, es gibt also noch gute Äpfel bevor sie bei der Oma ist. D.h. sie kommt bei der Oma mit Überschuss >= 1 an, was bedeutet, dass der im Korb liegende Apfel ein guter ist.

Gruss Otmar

[Friedel]

Mehr ->

Was ist denn M? Die Lösung ist einleuchtend und der Algorithmus führt zum Ziel. Aber die Begründung kann ich leider nicht nachvollziehen.

Es verbleiben N1 = N-2 M Äpfel, wobei noch G1 >= G-M gute Äpfel unter den N1 Äpfeln sein müssen.

Das halte ich für falsch. Die Zahl der guten Äpfel ist nicht bekannt. Angenommen, es sind insgesamt 5 Äpfel. Wenn die beiden ersten unterschiedlich schwer sind, können unter den noch verbleibenden 3 Äpfeln 3 gute sein oder eben 2 gute und ein schlechter. Egal, was M in der Formel ist, die Formel kann nicht stimmen.

Die Aufgabe hat mir sehr gut gefallen und tatsächlich ist die Lösung nicht nur verblüffend, sondern auch verblüffend einfach.

[Otmar]

@Friedel

Mehr ->

Also M ist die Zahl der Äpfel, die bis Überschuss 0 gleich schwer wie der erste Apfel waren (inklusive erster Apfel) und auch die Anzahl der bis dahin gefundenen Äpfel mit zum ersten Apfel anderem Gewicht. G1 >= G-M ist ja eine Ungleichung. Die sollte schon passen.

Die Beispiele von dir:

L S (Überschuss = 0) L L S

N = 5, G = 3, M = 1, N1 = 3, G1 >= 3-M

L S (Überschuss = 0) L L L

N = 5, G = 4, M = 1, N1 = 3, G1 >= 4-M

Da gilt das Gleichheitszeichen.

Die Zahl der guten Äpfel ist nicht bekannt.

Das ist richtig, auch die Zahl N der Äpfel überhaupt ist bei Überschuss 0 dem Rotkäppchen nicht bekannt. Aber es muss ja eine Zahle G geben, die die Anfangsbedingung erfüllt, und diese Zahl wird zur Begründung herangezogen.

Vielleicht sollte ich die Ungleichungskette des Induktionsschrittes noch aufschreiben:

G > N - G                nach Voraussetzung
G > (N1 + 2M) - G        wegen  N1 = N - 2M
G - M > N1 - (G - M)     auf beiden Seiten M subtrahiert
G1 > N1 - G1             da G1 >= G-M wurde die linke Seite höchstens größer und die rechte höchstens kleiner

Man könnte das auch einfach plausibel erklären. Nach Überschuss 0 haben die restlichen Äpfel immer noch eine Mehrheit an guten Äpfeln, da von den bisher gefundenen Äpfeln höchstens die Hälfte gut war.

Lg. Otmar

PS: Freut micht, dass dir die Aufgabe gefallen hat.

[Kolabord]

Das denke ich inzwischen auch, und dann ist die Lösung völlig[/spoiler]RICHTIG

Sorry, dass ich mich nicht früher gemeldet habe, aber Phoenix hat völlig recht und ich meinte das so, wie er erklärt hat.
Ein super Rätsel Otmar! Auch wenn mich ein wenig wundert, dass diesesmal gar kein Link zum Spektrummagazin angegeben ist, obwohl ich fest damit gerechnet hatte .

[Otmar]

Sorry, dass ich mich nicht früher gemeldet habe

Kein Grund für eine Entschuldigung, ich dachte, dass du das Rätsel in allen Punkten richtig lösen wolltest, auch in

Es ist Anfang Herbst...

und deshalb bis heute 11:04 MEZ mit der Antwort gewartet hast, denn da war Herbstanfang.

Auch wenn mich ein wenig wundert, dass diesesmal gar kein Link zum Spektrummagazin angegeben ist, obwohl ich fest damit gerechnet hatte

Da hatte ich es diesmal nicht entliehen, sondern eher aus der Informatikecke. Man kann z.B. "Majority algorithm" googeln. Da kommt es her. Das früheste, was ich dazu gefunden habe, ist noch mit Schreibmaschine getippt:
http://www.cs.utexas.edu/ftp/techreports/tr81-32.pdf
Leider nicht ganz so unterhaltsam wie die Spektrum Quellen, darum hab ich's erst auf Anfrage angegeben...

Gruß Otmar

[black]

Ich kann mich gar nicht entscheiden, ob ich das Rätsel oder die Lösung schöner finde. &

http://www.cs.utexas.edu/ftp/techreports/tr81-32.pdf
Leider nicht ganz so unterhaltsam wie die Spektrum Quellen, darum hab ich's erst auf Anfrage angegeben...

Und für ein Informatik-Skript ist es doch erstaunlich praxisorientiert.

Wobei die gesunde Ernährung einer Großmutter natürlich noch wichtiger ist.