Discussion:
Der Floh auf dem Zahlenstrahl
(zu alt für eine Antwort)
Rainer Rosenthal
2018-05-06 18:57:29 UTC
Permalink
Raw Message
Ein Floh springt auf dem Zahlenstrahl zu jeder Sekunde
stets in die gleiche Richtung, immer mit gleicher Sprungweite.

Beispiel:
t=0: Floh auf -4711
t=1: Floh auf -4715
t=2: Floh auf -4719
usw.
In diesem Fall startet der Floh bei -4711 und springt mit
jeder Sekunde 4 Schritte in negativer Richtung.

Ein Flohfänger möchte den Floh erlegen.
Immer wenn der Floh gesprungen ist, darf der Flohfänger
irgenwo auf den Zahlenstrahl klatschen.

Ewiges Leben und fantastische Ausdauer vorausgesetzt:
kann der Flohfänger mit Sicherheit den Floh treffen?

Ich danke Klaus Nagel für die Mitteilung dieses interessanten
Rätsels.

Lieb Grüße,
Rainer Rosenthal
***@web.de
Detlef Müller
2018-05-06 20:27:26 UTC
Permalink
Raw Message
Post by Rainer Rosenthal
Ein Floh springt auf dem Zahlenstrahl zu jeder Sekunde
stets in die gleiche Richtung, immer mit gleicher Sprungweite.
t=0: Floh auf -4711
t=1: Floh auf -4715
t=2: Floh auf -4719
usw.
In diesem Fall startet der Floh bei -4711 und springt mit
jeder Sekunde 4 Schritte in negativer Richtung.
Ein Flohfänger möchte den Floh erlegen.
Immer wenn der Floh gesprungen ist, darf der Flohfänger
irgenwo auf den Zahlenstrahl klatschen.
kann der Flohfänger mit Sicherheit den Floh treffen?
Wirkt ja erst einmal hoffnungslos für den Flohfänger.

Schränken wir den Floh im ersten Versuch also erst einmal ein:
er darf nur vorwärts hüpfen und muß bei 0 starten.

Dann kriegt ihn der Flohfänger wie folgt:
Er patscht im n-ten Versuch auf die Stelle n^2.

Wenn der Floh sich für die Schrittweite N entschieden hat,
wird er so im N-ten Versuch erwischt.

Ok. Nun erlauben wir dem Floh im zweiten Versuch, sich eine
Richtung auszusuchen, er muß aber wieder bei 0 starten.
Dann patscht der Fänger im 2n-1-ten Versuch auf n(2n-1) und im 2n-ten
Versuch auf -n*(2n), dann wird der Floh mit Hüpfweite N in positive
Richtung im 2N-1-ten Versuch erwischt und bei negativer Richtung im
2N-ten Versuch.

Nun können wir uns überlegen wie man ihn wirklich immer erwischt, also
auch wenn er an einem Beliebigen Ausgangspunkt A startet ... nach den
beiden Versuchsballons ahnen wir die Lösung schon.

Dafür nehmen wir eine Abzählung

q: IN --> Z \times Z, n |--> (q1(n), q2(n))

her (Z sollen die ganzen Zahlen sein, IN die natürlichen) und patschen
im n-ten Schritt auf die Stelle auf die Stelle (q1(n)+n*q2(n)).

Startet der Floh dann an Position A mit Schrittweite d, so ist
(A,d)=q(N) für ein N aus IN, da q ja surjektiv ist, und wir erwischen
den Floh in der Tat im N-ten Versuch (genau so wurde die Patsch-Stelle
gewählt).

Eine konkrete Formel auszurechnen wie in den ersten Versuchen ist
nun eine Fleißarbeit (aus der der Prof eine Übungsaufgabe macht :) )

Gruß,
Detlef
--
Dr. Detlef Müller,
http://www.mathe-doktor.de oder http://mathe-doktor.de
Martin Vaeth
2018-05-07 12:14:01 UTC
Permalink
Raw Message
Post by Detlef Müller
Nun können wir uns überlegen wie man ihn wirklich immer erwischt, also
auch wenn er an einem Beliebigen Ausgangspunkt A startet
Du nimmst hier an, dass A eine natürlich Zahl ist.
Ich bin nicht sicher, ob das mit "Zahlenstrahl" gemeint war.
Falls ja, kann man die Frage verallgemeinern und dadurch eine
einfachere Antwort geben.

Die verallgemeinerte Frage lautet:

Der Floh bewege sich gemäß einer Strategie S derart, dass er zum
Zeitpunkt n "auf" dem Element S(n) sitzt (n: natürliche Zahl).
Die Aufgabe des Flohfängers ist es, zu mindestens einem
Zeitpunkt n das richtige Element S(n) zu erwischen.
Außerdem sei ihm bekannt, dass die Strategie S des Flohs aus
einer abzählbaren Menge M stammt, die er kennt.
(In der Ursrpungsfrage hängt S nur von zwei abzählbaren Parametern ab -
Ausgangspunkt und Schrittweite - so dass M trivialerweise abzählbar ist).
Falls der Flohfänger sich dabei beliebig bewegen darf:
Wie kann er gewinnen?

Eine Antwort liefert die Diagonale:
Ist S_n (n=1,2,...) eine Abzählung von M, so muss der Flohfänger
im n-ten Schritt den Punkt S_n(n) erwischen.

(Detlevs Konstruktionen exerzieren das für konkrete Abzählungen
durch).

Natürlich kann man weiter verallgemeinern, etwa:
Nicht jeder "Treffer" sei ein erfolgreicher Fang. Der Flohfänger
möchte sich daher abzählbar viele "Treffer" sichern...
Helmut Richter
2018-05-06 22:37:47 UTC
Permalink
Raw Message
Post by Rainer Rosenthal
Ein Floh springt auf dem Zahlenstrahl zu jeder Sekunde
stets in die gleiche Richtung, immer mit gleicher Sprungweite.
t=0: Floh auf -4711
t=1: Floh auf -4715
t=2: Floh auf -4719
usw.
In diesem Fall startet der Floh bei -4711 und springt mit
jeder Sekunde 4 Schritte in negativer Richtung.
Ein Flohfänger möchte den Floh erlegen.
Immer wenn der Floh gesprungen ist, darf der Flohfänger
irgenwo auf den Zahlenstrahl klatschen.
Ganz einfach: er klatscht dort drauf, wo der Floh sitzt.

Hier scheint mir die Angabe zu fehlen, ob der Flohfänger
(a) die Sprungstrategie des Flohs oder
(b) die Flohposition zu irgendeinem Zeitpunkt kennt.

Außerdem gibt es keinen Punkt -4711 auf dem gewöhnlichen Zahlenstrahl.
Hier fehlt die Angabe, ob es sich vielleicht um eine Zahlengerade anstelle
eines Zahlenstrahls handelt und in dem Fall, dass es doch ein Strahl ist,
welche ganzen Zahlen er enthält.
--
Helmut Richter
H0Iger SchuIz
2018-05-07 13:51:03 UTC
Permalink
Raw Message
Post by Helmut Richter
Ganz einfach: er klatscht dort drauf, wo der Floh sitzt.
So etwas dachte ich mir auch. Vielleicht ist das Spiel nicht hinreichend
genau erklärt. Die Regel, dass er "irgendwo" auf den Zahlenstrahl
"klatsche" scheint mir da schon mal etwas Verbesserungspotenzial zu
bieten.

hs

Hans Crauel
2018-05-06 22:54:03 UTC
Permalink
Raw Message
Rainer Rosenthal schrieb
Post by Rainer Rosenthal
Ein Floh springt auf dem Zahlenstrahl zu jeder Sekunde
stets in die gleiche Richtung, immer mit gleicher Sprungweite.
t=0: Floh auf -4711
t=1: Floh auf -4715
t=2: Floh auf -4719
usw.
In diesem Fall startet der Floh bei -4711 und springt mit
jeder Sekunde 4 Schritte in negativer Richtung.
Ein FlohfÀnger möchte den Floh erlegen.
Immer wenn der Floh gesprungen ist, darf der FlohfÀnger
irgenwo auf den Zahlenstrahl klatschen.
kann der FlohfÀnger mit Sicherheit den Floh treffen?
Was weiss der Flohfaenger denn ueber den Floh? Wenn er
Anfangspunkt und Strategie kennt, ist es natuerlich klar.
Wenn er den Floh beobachten kann, kann er die Strategie
nach einigen Schritten herausfinden.

Wenn er gar nichts weiss, koennte er mit einer geeigneten
Verteilung, die jeder ganzen Zahl eine positive
Wahrscheinlichkeit zuweist, nach jedem Flohsprung zufaellig
und unabhaengig eine Position zum Klatschen auswaehlen. Die
Wahrscheinlichkeit, den Floh nicht zu treffen, waere dann
Produkt der Einzel-Wahrscheinlichkeiten. Wenn der Floh immer
mit gleicher Sprungweite springt, gibt es m.E. Verteilungen,
mit denen man dieses Produkt zu Null kriegt, so dass man den
Floh mit Wahrscheinlichkeit 1 irgendwann trifft. Die
Normalverteilung (bzw. eine geeignete Diskretisierung) tut
es moeglicherweise nicht, weil die Wahrscheinlichkeiten grosser
Zahlen zu schnell klein werden. Man muesste wohl was mit
"heavy tail" nehmen. Springt der Floh jedoch zunehmend schneller
(z.B. in der n-ten Sekunde e^n Schritte), findet man
moeglicherweise keine.
Angaben ohne Gewaehr; Antwort erfolgte ohne tiefes Nachdenken.

Hans
Loading...