5
$\begingroup$

This puzzle is the continuation and second part of: "A final incident in the flea circus: Part 1"


The ringmaster of a flea circus draws a square $ABCD$ with corners $A=(+1,+1)$, $B=(+1,-1)$, $C=(-1,+1)$, $D=(-1,-1)$ in the Euclidean plane and picks a point $P$ with two non-integral coordinates outside the square. The ringmaster then places a flea onto point $P$.

Whenever the ringmaster shouts "Hop!", the flea looks around itself, picks the rightmost vertex of the square (from its current point of view), and then jumps over this rightmost vertex to the mirror point on the other side. (In other words, the flea sitting in point x may jump over the rightmost vertex y to the new point z, so that y is the midpoint between x and z.)

Question: Is it possible that after a finite number of jumps the flea reaches a point $Q$, so that the distance between origin and $Q$ is at least $30$ times the distance between origin and $P$?

$\endgroup$
  • 1
    $\begingroup$ You tagged this question combinatorics, but my answer didn't end up using any. I hope you like the approach I went with anyway! $\endgroup$ – Lynn Nov 5 '15 at 20:25
4
$\begingroup$

This is a continuation of my previous answer. The answer is no: if we consider only the non-integral points inside the eight regions of $f^2$, we see the flea will always take on a bounded path.

The eight regions $f^2$ acts differently on are snapped to an orthogonal grid, where each grid cell is a $2 \times 2$ square, and the origin is the center of a cell. We will consider only the interior of these squares, as we're examing non-integral coordinates.

Because of this grid the regions are laid out on, each cell has the property that all of its points will undergo the same transformation when $f^2$ is applied to them. Because all of the transformations in the piecewise definition of $f^2$ are translations over a vector whose components are both multiples of 2, the entire cell is even mapped to a different cell!

Another way to state this is to say that the value of $\operatorname{fmod}(x+1, 2)$ and $\operatorname{fmod}(y+1, 2)$ doesn't affect the shape of the path the flea will take when starting at $(x, y)$; only which cell the initial point falls in matters. (fmod, here, is fractional modulo.)

As an example, here are the paths the flea takes when starting from two points in the same cell (the gray lines mark the cells; the center cell containing the origin is the square the flea jumps over):

$\hspace2in$coinciding paths http://puu.sh/laBEY/3dd820c323.png

We must prove that for all of these cells, the path will be bounded. Here is the grid of cells, with arrows representing the direction of the translation $f^2$ will move the flea in by two cells from any point in the cell:

$\hspace1.2in$cell directions

Without loss of generality, assume the flea is in the center of the cells. Then it is clear to see that none of the possible moves will change the effective taxicab distance between the flea and the origin: the diagonal moves would have never changed it anyhow, and the orthogonal moves nicely mirror the flea's position over one of the axes. The ratio between the taxicab norm and the regular norm is at most $\sqrt{2}$, so we can never stray more than $\sqrt{2}$ times as far away from the origin as from the initial point.

To account for the fact that the flea might not be exactly in the center of a cell, and the actual norms will fluctuate, note that moving the flea around within a cell will not matter: the largest factor that can ever account for is the difference between the flea being in the center at $(2, 0)$ vs. it being very close to $(3, 1)$, where the ratio is $\frac{\sqrt{3^2+1^2}}{\sqrt{2^2+0^2}}=\sqrt{5}$, and $\sqrt{2} \cdot \sqrt{5} < 30$ still.

(Edit: I suppose this only proves that the subsequence of double jumps is bounded in norm. Can the norm "peak" in the transitional jump between two of the jumps we did count? No: $f$ itself is a rotation, which doesn't affect the norm, followed by a translation over $(\pm 2,\pm 2)$. The worst ratio this could account for is bounded above by $\sqrt{13}$ by similar logic to the above. (Imagine the flea moves from a point close to (1, 0) to a point close to a rotation of (3, 2).) Stacking all of these weird upper bounds, we can only account for a total ratio of at most $\sqrt 2 \cdot \sqrt 5 \cdot \sqrt{13}$, which is still less than 30.)

$\endgroup$
1
$\begingroup$

Yes. In the first part, we had to choose a point $P^{'}$ with integral coordinates, and it's easy to see that we can choose $P^{'}$ such that 'hopping' is continuous in a neighborhood of $P^{'}$. Then, if we pick $P$ close enough to $P^{'}$ in that neighborhood, continuity ensures all is well.

$\endgroup$
  • $\begingroup$ Do you have a proof for the "it is easy to see" part? $\endgroup$ – Gamow Nov 4 '15 at 18:42
  • $\begingroup$ It suffices to see that we can choose $P^{'}$ such that small perturbations to $P^{'}$ will not change the rightmost vertex. That mirroring is continuous is agreed upon, I suppose? $\endgroup$ – Fimpellizieri Nov 4 '15 at 19:06
  • $\begingroup$ I am not sure I understand you. Do you want to say it's not clear that $P^{'}$ can be chosen such that the rightmost vertex (in relation to it) is fixed in a neighborhood of $P^{'}$? $\endgroup$ – Fimpellizieri Nov 5 '15 at 18:46
  • $\begingroup$ It is not necessary for the flea to sit on the same line as two corners. You can have the flea start on $(3,2)$, for instance. $\endgroup$ – Fimpellizieri Nov 5 '15 at 21:30
  • $\begingroup$ Alright, I made a program to test it, and I think I can see what's wrong with my reasoning. For instance, after 3 iterations, $(3,2)$ goes to $(-1,4)$ which is in one of the lines with two corners. I believe this holds true for any point with integral coordinates where at least one of the coordinates is odd; for those where both coordinates are even, I believe iterations are cyclical. $\endgroup$ – Fimpellizieri Nov 5 '15 at 22:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.