0
$\begingroup$

Based on Another curious incident in the flea circus and A curious incident in the flea circus by @Gamow

There is a $n$ dimensional cube in an $n$ dimensional world. There is a flea on each vertex of the hypercube. When the ringmaster shouts "Hop!", any one flea at a point $A$ selects any other flea at another point $B$ and jumps to a point $C$ such that $AB=BC=\frac12AC$. Two fleas may sit at the same point in space.

Is it possible that after some time, there are $3$ fleas sitting on points on a straight line?

$\endgroup$
  • $\begingroup$ Perhaps in an $n+1$ dimensional world? $\endgroup$ – dmg Oct 27 '15 at 9:18
  • $\begingroup$ @dmg How does the number of dimensions of the world matter as long as it is $\geq$ dimensions of the cube? $\endgroup$ – ghosts_in_the_code Oct 27 '15 at 10:50
  • $\begingroup$ Well they'll have to be flying fleas if $n = 3$. Which can be generalized to "flying fleas" in whatever $n$. $\endgroup$ – dmg Oct 27 '15 at 11:24
9
$\begingroup$

No; the argument that works in the 2-dimensional case works with essentially no change in $n$ dimensions.

Select a coordinate system such that the $2^n$ fleas start out at positions $\{0,1\}^n$.

Paint the integer points on the lattice in $2^n$ different colors based on the parity of their coordinates -- that is, the point $(x_1,\ldots,x_n)$ will have the same color as $(x_1 \bmod 2,\ldots, x_n \bmod 2)$.

Every flea jump changes each of the flea's coordinates by an even number, so each flea stays on the color it started out on (and all fleas are on different colors to begin with).

Like in the 2D case, any straight line containing two different lattice points will contain points from of exactly two colors, so there are only two of the fleas that can even reach a position on the line.

Why only two colors on a line? Write the parametric equation for the line as $$(x_1,\ldots,x_n) = (a_1,\ldots,a_n)+t(p_1,\ldots,p_n), \quad t\in \mathbb R$$ Without loss of generality all of the $a_i$s and $p_i$s can be integers, and we can also assume that $\gcd(p_1,\ldots,p_n)=1$ (otherwise divide through by the gcd, and scale the $t$s appropriately). This means that the lattice points on the line will be exactly those with integer $t$. When this $t$ is even, the point has the same color as $(a_1,\ldots,a_n)$, and when $t$ is odd it has the same color as $(a_1+p_1,\ldots,a_n+p_n)$.


(This argument works even in an 1-dimensional world, although there it is trivial that we can't have three collinear fleas because there are only two fleas in total!)

$\endgroup$

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.