Discussion:
Der Floh auf der Zahlengerade
(zu alt für eine Antwort)
Rainer Rosenthal
2018-05-07 20:48:48 UTC
Permalink
Ein Floh springt auf der Zahlengeraden (alle ganzen Zahlen) 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 die Zahlengerade 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. Danke auch für den Hinweis, dass die ganzen Zahlen nicht
als Zahlenstrahl, sondern als Zahlengerade zu bezeichnen sind.
Die wesentlichen Gedanken hat Detlef Müller gebracht, Gratulation!

Liebe Grüße,
Rainer Rosenthal
***@web.de
Stefan Ram
2018-05-08 09:52:06 UTC
Permalink
Post by Rainer Rosenthal
Die wesentlichen Gedanken hat Detlef Müller gebracht, Gratulation!
Nachdem ich Detlefs Posting gelesen habe, hier ein Versuch,
das ganze in meinen Worten zu erklären (wenn ich es
überhaupt richtig verstand habe):

Man kann eine Tabelle anlegen, welche die Startposition des
Flohs (P) und die Schrittweite des Flohs (W) enthält:

P W
0 0
1 0
0 1
1 1
-1 0
-1 1
-1 -1
...

Die Menge der Paare (P, W) ist /abzählbar/. Entscheidend
ist, daß sie /nicht überabzählbar/ ist. Daher können wir die
unendlich vielen Zeilen der Tabelle in einer Weise
anordnen, die /jede mögliche/ Zeile enthält.

Nun kann man die Tabelle von Anfang an durchgehen und aus P,
W und der aktuellen Zeit die aktuelle Position des Flohs
berechnen und dorthin schlagen.

Da /jede/ mögliche Kombination ( P, W ) in der Tabelle
enthalten ist, wird damit /irgendwann einmal/ der Floh
getroffen werden. Freilich könnte dies in der Praxis
eine Weile dauern!
Rainer Rosenthal
2018-05-08 13:54:51 UTC
Permalink
Post by Stefan Ram
Post by Rainer Rosenthal
Die wesentlichen Gedanken hat Detlef Müller gebracht, Gratulation!
Nachdem ich Detlefs Posting gelesen habe, hier ein Versuch,
das ganze in meinen Worten zu erklären (wenn ich es
Hast Du.

Und ich habe auch eine Lösungsformulierung anzubieten.
Die Parametersätze sind abzählbar, und zum n-ten Parametersatz
gehört der "Fahrplan" F(n). F(n)(t) gibt den Ort des Flohs zur
Zeit t an, wenn er gemäß diesen Parametern springt.
Schlägt man immer zur Zeit t auf den Ort F(t)(t), dann erwischt
man den Floh.

Mir gefiel diese Einkleidung des Diagonalarguments von Cantor.
Interessierte Kinder könnten daran Gefallen finden.

Die von Detlef genannte alternative Fortbewegungsart mit frei
wählbarem Richtungswechsel wollte ich eigentlich demnächst
auch noch in folgender Form bringen:
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Die Mücke auf der Zahlengeraden
-------------------------------
Eine Mücke (pun intended) hüpft auf der Zahlengeraden von
einem unbekannten Startplatz in positiver Richtung, wobei sie
pausieren darf. In jeder Sekunde entscheidet sie sich also
für Sprung oder Verweilen.
Gibt es eine "todsichere" Strategie, sie zu erschlagen?
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Gruß,
Rainer
Helmut Richter
2018-05-08 10:01:37 UTC
Permalink
Post by Rainer Rosenthal
Ein Floh springt auf der Zahlengeraden (alle ganzen Zahlen) 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 die Zahlengerade klatschen.
kann der Flohfänger mit Sicherheit den Floh treffen?
Ich kann in dieser Iteration der Aufgabenstellung immer noch keine
Spielregel entdecken, die beschreiben würde, welche Information der
Flohfänger über die Position oder die Sprünge des Flohs hat. Damit kann
der Flohfänger auf eine beliebige Stelle klatschen, insbesondere auf die,
wo der Floh sitzt. In einem Schritt gelöst – trivial.
--
Helmut Richter
Valentin Schmidt
2018-05-08 10:22:13 UTC
Permalink
Post by Helmut Richter
Ich kann in dieser Iteration der Aufgabenstellung immer noch keine
Spielregel entdecken, die beschreiben würde, welche Information der
Flohfänger über die Position oder die Sprünge des Flohs hat. Damit kann
der Flohfänger auf eine beliebige Stelle klatschen, insbesondere auf die,
wo der Floh sitzt. In einem Schritt gelöst – trivial.
Da das wohl einige nicht richtig interpretieren konnten, folgendes hatte
der OP bei der Aufgabe noch stillschweigend vorausgesetzt:

Der Flohfänger hat weder extrem gute Augen noch eine Lupe, er kann den
Floh also *nicht* sehen. Er weiß einzig und allein, dass der Floh sich
strickt gemäß beschriebener Regel fortbewegt, kennt aber weder
Anfangsposition noch Sprungweite/Sprungrichtung.

Ich hoffe das macht es klarer.
Stefan Ram
2018-05-08 10:33:19 UTC
Permalink
Post by Valentin Schmidt
Da das wohl einige nicht richtig interpretieren konnten, folgendes hatte
Der Flohfänger hat weder extrem gute Augen noch eine Lupe, er kann den
Floh also *nicht* sehen. Er weiß einzig und allein, dass der Floh sich
strickt gemäß beschriebener Regel fortbewegt, kennt aber weder
Anfangsposition noch Sprungweite/Sprungrichtung.
Danke.

Man muß in solche Fällen alle nicht angegebenen Details
durchprobieren. In einigen Fällen ist die Aufgabe unter
bestimmten Interpretationen dann entweder trivial oder
offensichtlich unlösbar. So ergibt sich dann oft eine
einzige mögliche Interpretation.

Man kann dies auch als eine Art "Meta-Rätsel" oder
als Teil der Aufgabe ansehen.

Die Äußerungen von Menschen sind fast immer mehrdeutig.
Der Hörer wählt aus den verschiedenen Interpretation durch
ein ähnliches Verfahren die richtige aus. Dies setzt eine
gewisse Bereitschaft voraus, die manchmal scherzhaft
weggelassen wird:

A: "Sag mal, wie spät ist es jetzt eigentlich?"
B: "Mal, wie spät ist es jetzt eigentlich?"

.
Stefan Ram
2018-05-08 11:49:46 UTC
Permalink
Post by Valentin Schmidt
Der Flohfänger hat weder extrem gute Augen noch eine Lupe, er kann den
Floh also *nicht* sehen.
Allerdings wollen wir annehmen, daß er es bemerkt,
/falls/ er den Floh bei einem Schlag getroffen haben
sollte, damit er dann aufhören kann.
Rainer Rosenthal
2018-05-08 11:45:59 UTC
Permalink
"Mit Sicherheit". Nicht aufgeben! Detlef Müllers Beitrag nur im Notfall lesen.
Detlef Müller
2018-05-08 11:50:26 UTC
Permalink
Post by Helmut Richter
Post by Rainer Rosenthal
Ein Floh springt auf der Zahlengeraden (alle ganzen Zahlen) zu jeder
Sekunde stets in die gleiche Richtung, immer mit gleicher Sprungweite.
[...]
Post by Helmut Richter
Post by Rainer Rosenthal
Ein Flohfänger möchte den Floh erlegen.
Immer wenn der Floh gesprungen ist, darf der Flohfänger
irgenwo auf die Zahlengerade klatschen.
kann der Flohfänger mit Sicherheit den Floh treffen?
Ich kann in dieser Iteration der Aufgabenstellung immer noch keine
Spielregel entdecken, die beschreiben würde, welche Information der
Flohfänger über die Position oder die Sprünge des Flohs hat.
In der Tat ist das nicht bekannt.
Post by Helmut Richter
Damit kann
der Flohfänger auf eine beliebige Stelle klatschen, insbesondere auf die,
wo der Floh sitzt. In einem Schritt gelöst – trivial.
Nun, wenn Dich diese Lösung zufrieden stellt,
Gratuliere.

Andere könnten nun damit Spielen, wie viel Information der Fänger
hat, welche Strategien dann zum Ziel führen könnten und ab wann
nichts mehr geht.
Sobald der Fänger einen Teil der "Floh-Strategie" nicht kennt, wird
es ja erst interessant.

Das Ergebnis, daß es selbst wenn beide Parameter unbekannt sind, aber
der Fänger zumindest die allgemeine Strategie kennt, möglich ist, den
Floh sicher zu erwischen, ist zumindest für mich wesentlich
interessanter und befriedigender.
Die Meta-Information, daß Rainer stets interessante Knobelaufgaben
beizutragen pflegt hat mich eher zu dieser Interpretation
veranlasst :)
Wie Martin bemerkt hat, läuft es darauf hinaus, daß eine abzählbare
Menge von (deterministischen) Floh-Strategien S (und natürlich die
Info, daß der Floh sich an eine davon halten muß) dem Floh keine
Chance lässt.

Hat der Floh z.B. nur eine maximale Sprungweite (>0) und einen
Ausgangsbereich vorgegeben, ist die Anzahl seiner Wege nicht
mehr abzählbar. Man kann dann womöglich stochastische
Überlegungen machen, wo dann sicher auch wichtig ist, ob der Floh
schlau ist und ob er die Strategie seines Häschers kennt ... jedes nicht
randomisierte Vorgehen wird der Floh dann natürlich durchkreuzen
können.

Springt der Floh immer um 1 vor oder zurück, was er mit jedem Sprung
neu entscheidet, kann man ihn "fast sicher" (d.h mit Wahrscheinlichkeit
1) mit einer randomisierten Strategie fangen, wenn sein Startpunkt
bekannt ist (und er natürlich den ersten Sprung hat).

Gruß,
Detlef
Stefan Ram
2018-05-08 12:23:01 UTC
Permalink
Post by Detlef Müller
Hat der Floh z.B. nur eine maximale Sprungweite (>0) und einen
Ausgangsbereich vorgegeben, ist die Anzahl seiner Wege nicht
mehr abzählbar. Man kann dann womöglich stochastische
Überlegungen machen,
Ich stelle mir intuitiv vor, daß das Maß einer abzählbaren
Teilmenge in einer überabzählbaren Menge gleich 0 ist, so
daß die Wahrscheinlichkeit, daß ein allgemeiner Punkt der
überabzählbaren Menge in der abzählbaren Menge liegt, gleich
0 ist.

Suchmaschinen finden jedenfalls folgendes Zitat
(Formatierungen automatisch von PDF nach Text gewandelt):

|Jede abzählbare Teilmenge A ⊆ Rn ist eine Borelmenge vom Maß
|λ(A) = 0, also insbesondere eine λ-Nullmenge. Hier benutzt
|man, daß einpunktige Teilmengen {x} ⊆ R Borelmengen vom Maß
|0 sind; A ist eine abzählbare Vereinigung solcher Mengen.

.
Rainer Rosenthal
2018-05-08 12:46:00 UTC
Permalink
Huch, wenn der Floh zwischen +1 und -1 wählen darf, gibt es garantiert keine Strategie, um ihn sicher zu treffen.

Interessant, dass es aber "fast sicher" möglich sein soll. Könntest Du das bitte erläutern.

Danke für das Lob, dass meine Aufgaben i.A. lesens- und lösenswert sind. Berechtigte Kritik an der Aufgabenstellung nehme ich gerne an.

Wenn in der Aufgabe aber nach "sicher fangen" gefragt ist, dann sind Lösungen mit Zufallselement bestimmt unerwünscht.
Um die Qualität der Aufgabe zu unterstreichen, habe ich extra darauf hingewiesen, dass sie mir von Klaus Nagel mitgeteilt wurde. Sie stammt nicht von ihm, aber er fand sie mitteilenswert.

Gruß,
Rainer
Detlef Müller
2018-05-08 14:59:36 UTC
Permalink
Post by Rainer Rosenthal
Huch, wenn der Floh zwischen +1 und -1 wählen darf, gibt es
garantiert keine Strategie, um ihn sicher zu treffen > Interessant, dass es aber "fast sicher" möglich sein soll. Könntest
Du das bitte erläutern.
Natürlich muß der Ausgangsort, sagen wir 0 bekannt sein.

Nach dem ersten Sprung ist er dann auf 1 oder -1, man
patscht auf 1 (oder -1 und fährt sinngemäß fort).
Hat man ihn nicht erwischt, muß er auf -1 gewesen sein.

Nach dem nächsten Sprung steht er dann auf -2 oder 0, man
patscht auf -2.

Wenn er dann noch lebt, stand er garantiert auf 0, wir
sind wieder in der Ausgangssituation und können nun wieder
von vorn anfangen ... dabei wird randomisiert 1 und -1
gewählt (damit der Floh keine Gegenstrategie hat) und jedes
mal halbiert sich seine Überlebenswahrscheinlichkeit.

Hier hat man Glück, daß eine kombinatorische Besonderheit
dazu führt, daß der Floh, so er noch lebt, zu einem bestimmten
Zeitpunkt garantiert auf 0 steht.

Es gibt ein in dem Sinne verwandte Knobelei (über die ich bei
youtube gestolpert bin), bei der eine Katze
in einem von 5 Kartons sitzt, welche nebeneinander stehen.
Man darf dann immer in einem Karton nachschauen (findet man die
Katze, hat man gewonnen und das Spiel ist zu ende).
Nach dem Nachschauen (über Nacht) wechselt die Katze von ihrem
momentanen Karton in einen Nachbarkarton (natürlich unbemerkt
und bleibt nie einfach sitzen).
Gefragt ist die minimale Anzahl an Proben, die man braucht,
um die Katze zu ertappen (lässt sich auch auf n Kartons
ausbauen).
Erinnert mich ein wenig an das Spiel "Scotland Yard", extreme
Sparversion :)

[...]
Post by Rainer Rosenthal
Wenn in der Aufgabe aber nach "sicher fangen" gefragt ist, dann sind
Lösungen mit Zufallselement bestimmt unerwünscht. Um die Qualität der
Aufgabe zu unterstreichen, habe ich extra darauf hingewiesen, dass
sie mir von Klaus Nagel mitgeteilt wurde. Sie stammt nicht von ihm,
aber er fand sie mitteilenswert.
Sobald Zufall oder gar irgendwelche Maßtheorie ins Spiel kommt
habe ich großen Respekt ... da ist man schnell verleitet herum
zu fabulieren, obwohl gar nicht klar ist, was überhaupt der
W-Raum sein soll, wie die Verteilungen und Gewichte aussehen
etc.

Wenn so ein Problem dann endlich in aller Präzision und vollständig
formuliert ist, haben sicher viele schon keine Lust mehr,
sich nach der langen Vorrede überhaupt der eigentlichen Lösung
zuzuwenden ...

Gruß,
Detlef
--
Dr. Detlef Müller,
http://www.mathe-doktor.de oder http://mathe-doktor.de
Rainer Rosenthal
2018-05-08 18:38:07 UTC
Permalink
Post by Detlef Müller
Post by Rainer Rosenthal
Huch, wenn der Floh zwischen +1 und -1 wählen darf, gibt es
garantiert keine Strategie, um ihn sicher zu treffen > Interessant,
dass es aber "fast sicher" möglich sein soll. Könntest
Du das bitte erläutern.
Natürlich muß der Ausgangsort, sagen wir 0 bekannt sein.
Gut, einverstanden.
Post by Detlef Müller
... und jedes
mal halbiert sich seine Überlebenswahrscheinlichkeit.
Auch einverstanden.
Jetzt weiß ich, wie Du "fast sicher" gemeint hast, und das
Verfahren ist lustig.

Ohne den bekannten Ausgangsort klappt es aber nicht, oder?

Der fundamentale Unterschied zur "todsicheren" Lösung ist:
In der Originalaufgabe gibt es eine natürliche Zahl N, so dass
der Floh nach N Hüpfern erledigt ist.

So ein N gibt es beim Plusminus-Floh nicht.

Gruß,
Rainer

P.S.
Ich werde die Mücken-Aufgabe bald offiziell posten, aber es war
gut, das schon vorab ins Unreine getan zu haben. Die Mücke soll
nämlich nur um 0 oder 1 weitersausen. Selbst bei bekanntem Startort ist
sie nicht sicher fangbar.
Valentin Schmidt
2018-05-08 20:21:29 UTC
Permalink
Post by Rainer Rosenthal
P.S.
Ich werde die Mücken-Aufgabe bald offiziell posten, aber es war
gut, das schon vorab ins Unreine getan zu haben. Die Mücke soll
nämlich nur um 0 oder 1 weitersausen. Selbst bei bekanntem Startort ist
sie nicht sicher fangbar.
Den Satz "Selbst bei bekanntem Startort ist sie nicht sicher fangbar"
kapiere ich grade nicht so ganz. Aber unabhängig davon: was bei der
Mücken-Aufgabe glaube ich noch geklärt werden müsste: wenn, falls ich es
richtig verstehe, Mückenbewegung und Mückenklatscher-Aktionen
abwechselnd stattfinden, was genau passiert, wenn Mücke sich auf den
zuletzt geklatschten Ort bewegt? Kann sie das, ohne Schaden zu nehmen?
Rainer Rosenthal
2018-05-08 20:39:45 UTC
Permalink
Post by Valentin Schmidt
Post by Rainer Rosenthal
P.S.
Ich werde die Mücken-Aufgabe bald offiziell posten, aber es war
gut, das schon vorab ins Unreine getan zu haben. Die Mücke soll
nämlich nur um 0 oder 1 weitersausen. Selbst bei bekanntem Startort ist
sie nicht sicher fangbar.
Den Satz "Selbst bei bekanntem Startort ist sie nicht sicher fangbar"
kapiere ich grade nicht so ganz. Aber unabhängig davon: was bei der
Mücken-Aufgabe glaube ich noch geklärt werden müsste: wenn, falls ich es
richtig verstehe, Mückenbewegung und Mückenklatscher-Aktionen
abwechselnd stattfinden, was genau passiert, wenn Mücke sich auf den
zuletzt geklatschten Ort bewegt? Kann sie das, ohne Schaden zu nehmen?
Ja, dann setzt sie sich frech auf die Hand :-)
Formale Einkleidung:

Wir haben eine Funktion M : {0,1,2,3,...} -> {0,1,2,3,...}
mit M(0) = 0 und M(i+1) = M(i) oder M(i)+1.
Das steht für die Mückenbewegung, es ist M(t) der Ort zur Zeit t.

Gesucht ist eine Funktion K : {1,2,3,...} -> {0,1,2,3,...} derart,
dass es mindestens ein t > 0 gibt mit K(t) = M(t).
Das steht für das Klatschen: zur Zeit t wird auf K(t) geklatscht.

Wenn die Formalisierung genehm ist, dann kannst Du gerne einen
Vorschlag machen, wie man das umgangssprachlich korrekt fasst.

Es ist recht spät, vielleicht war das Blödsinn :-)

Liebe Grüße,
Rainer
Detlef Müller
2018-05-09 13:43:32 UTC
Permalink
Post by Rainer Rosenthal
Post by Detlef Müller
Post by Rainer Rosenthal
Huch, wenn der Floh zwischen +1 und -1 wählen darf, gibt es
garantiert keine Strategie, um ihn sicher zu treffen > Interessant,
dass es aber "fast sicher" möglich sein soll. Könntest
Du das bitte erläutern.
Natürlich muß der Ausgangsort, sagen wir 0 bekannt sein.
Gut, einverstanden.
Post by Detlef Müller
... und jedes
mal halbiert sich seine Überlebenswahrscheinlichkeit.
Auch einverstanden.
Jetzt weiß ich, wie Du "fast sicher" gemeint hast, und das
Verfahren ist lustig.
Ohne den bekannten Ausgangsort klappt es aber nicht, oder?
Selbst wenn der Floh auf einer von zwei bekannten, nebeneinander
liegenden Positionen, etwa 0 und 1 sitzt (und man natürlich nicht
weiß auf welcher), bin ich ziemlich sicher, daß er Chancen (>0) hat,
zu entwischen.
Eine Beweisidee wäre zu zeigen, daß die Anzahl der möglichen Positionen,
wo man auch hinpatscht immer um 1 wächst und darauf eine Argumentation
aufzubauen.

Sollte es dennoch eine Strategie geben, ihn "fast sicher" zu fangen,
wäre ich ein wenig erstaunt ... aber in die Gefilde der W-Theorie mit
Markov-Ketten etc. will ich mich jetzt nicht begeben :)
Andererseits ist vermutlich für jeden, der sich noch nicht mit
Abzählbarkeits-Themen beschäftigt hat sicher auch überaschend, daß
es im original Rätsel eine sichere Möglichkeit gibt.

Startet der Floh aber zufällig auf 0 oder 2, kann man ihn durch
abwechselndes patschen auf 3 und -2 immernoch in seinem Bereich
festhalten. Sollte er stets in eine zufällige Richtung hüpfen,
kriegt man ihn auch dann fast sicher nach dem Motto "irgendwann
hüpfte er schon ins Verderben".
Ist dem Floh die Strategie bekannt und er versucht sie zu
durchkreuzen, bekommt man ihn allerdings sogar garantiert
nicht.

All das wird sowieso hinfällig, wenn man dem Floh auch ein sitzen
bleiben erlaubt, dann geht ja nicht einmal mehr die Strategie bei
bekanntem Ausgangspunkt.
Post by Rainer Rosenthal
In der Originalaufgabe gibt es eine natürliche Zahl N, so dass
der Floh nach N Hüpfern erledigt ist.
So ein N gibt es beim Plusminus-Floh nicht.
Genau.

Gruß,
Detlef
--
Dr. Detlef Müller,
http://www.mathe-doktor.de oder http://mathe-doktor.de
Rainer Rosenthal
2018-05-09 17:23:48 UTC
Permalink
Post by Detlef Müller
Post by Rainer Rosenthal
So ein N gibt es beim Plusminus-Floh nicht.
Genau.
Hallo Detlef, danke fürs Mitmachen und das Aussch-mücken :-)

Ich habe inzwischen einen Interessenten gefunden, der sich
die konkreten Klatsch-Orte zu gegebenen Aufzählungen durch-
rechnet und daraus Folgen für die OEIS herstellen will.
Er hat nach der Quelle des Rätsels gefragt, und ich habe
ihn an Klaus Nagel verwiesen, der die Aufgabe auch nicht
erfunden, sondern gehört hatte.
Wenn ich die Quelle erfahre, teile ich sie hier auch noch
gerne mit. Das Mücken-Problem lasse ich noch ruhen.

Liebe Grüße,
Rainer Rosenthal,
***@web.de
Carlo XYZ
2018-05-09 18:41:14 UTC
Permalink
Post by Rainer Rosenthal
Wenn ich die Quelle erfahre, teile ich sie hier auch noch
gerne mit.
Das hier scheint zumindest ein naher Verwandter zu sein:

<https://math.stackexchange.com/questions/1792736/flea-on-the-coordinate-system/2359293#2359293>
Post by Rainer Rosenthal
Das Mücken-Problem lasse ich noch ruhen.
Sehr weise.
Rainer Rosenthal
2018-05-09 20:30:59 UTC
Permalink
Post by Carlo XYZ
<https://math.stackexchange.com/questions/1792736/flea-on-the-coordinate-system/2359293#2359293>
Der Autor des Englischen Texts ist Spanier, und es ist zu vermuten,
dass er selbst diese Aufgabe irgendwo aufgeschnappt hat.
Aus irgendwelchen Gründen kann ich von der genannten Website nicht
kopieren. Ich tippe also ab, denn gar so schlecht ist der Text nicht,
und als Dreingabe darf der Floh auch noch in einem anscheinend
zweidimensionalen Gitter herumhupfen, auch nur in einer Richtung,
allerdings nur um Betrag 1.

Ich habe mir erlaubt, das sinnentstellende "infinitely" in "finitely" zu
ändern.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
We drop a flea on a point of the coordinate system (with integer
coordinates). Due to the dimensions of the flea we cannot see it. The
flea jumps away every second by one unit (always in the same direction).
We can choose a point every second and if the flea is on that point at
that particular second we have caught it. Is it possible to catch the
flea in finitely {sic!] many steps?
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Sehr knackig und gut ist diese Antwort:
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Well, there is a countably infinite integer plane for initial positions
and finite number of directions, which together make a countably
infinite list of possible trajectories of the flea. Why can't we just
traverse that list, hitting n'th point on the n'th trajectory at the
moment n? - Ivan Neretin May 20 '16 at 10:58
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Sie ist perfekt formuliert und passt auf allerlei Variationen, wie z.B.
die mir erzählte Version auf der Zahlengeraden.
Die Vielfalt lässt sich in dem Gitterbeispiel nochmal (scheinbar)
drastisch erhöhen, wenn man dem Floh jede Richtung erlaubt, in der er
wieder zu einem Gitterpunkt gelangt.

Gruß,
Rainer

Loading...