11
$\begingroup$

The ringmaster of a flea circus puts four fleas $A$, $B$, $C$, $D$ on four different points in the plane that form the corners of a square.

  • Whenever the ringmaster shouts "Hop!", one of the four fleas jumps over one of the other fleas to the mirror point on the other side. (In other words, a flea sitting in point $x$ may jump over a flea sitting in point $y$ to the new point $z$, so that $y$ is the midpoint between $x$ and $z$.)
  • While the fleas are jumping around, sometimes two of them may be sitting simultaneously on the same point. (This is fine, as these fleas are infinitesimally small.)

Question: Is it possible that after some time the three fleas $A$, $B$ and $C$ are sitting in points on the same straight line?

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ Yada yada yada, something about infinity... Great question, though :) $\endgroup$
    – dmg
    Oct 26, 2015 at 11:13
  • $\begingroup$ Does "after some time" allow for an infinite number of jumps? $\endgroup$
    – Todd Wilcox
    Oct 26, 2015 at 16:50
  • $\begingroup$ Upon further reflection I don't think it makes a difference, but it's good to have it on the record anyway. $\endgroup$
    – Todd Wilcox
    Oct 26, 2015 at 17:17

4 Answers 4

Reset to default
17
$\begingroup$

This answer is entirely due to Henning Makholm.

If we draw a grid in such a way that the four fleas are at positions $(0,0), (0,1),(1,0)$ and $(1,1)$, then the fleas will forever be at integer points on the grid.

Color the lattice points red, blue, green and purple by repeating the pattern

The key observation is that a flea will always hop to the same color lattice point it starts on. This is because hopping changes both its coordinates by a multiple of two, meaning the parity of both its coordinates are preserved, and these parities determine the point's color.

Furthermore, any line of lattice points will only consist of two colors. Since any three fleas are always on three different colors (they start out this way, and the colors never change), this means three fleas can never be on a line.

Why only two colors on a line? Write the parametric equation for the line as $$(x,y) = (a,b)+t(p,q), \quad t\in \mathbb R$$ If the line contains at least two lattice points (otherwise it would be uninteresting for us here), we can chose all of $a,b,p,q$ as integers, and we can also choose $p$ and $q$ to be coprime, in which case 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,b)$, and when $t$ is odd it has the same color as $(a+p,b+q)$.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ @HenningMakholm I've turned the solution in your comment into an answer, since it is a beautiful proof which deserves more attention. If this is against your wishes, or you wanted to do the same, I will delete this. $\endgroup$
    – Mike Earnest
    Oct 26, 2015 at 18:46
  • 1
    $\begingroup$ This is a beautiful proof. However, I think it may need a little fleshing out as to why you can't have a line with all four colours in where that line is neither horizontal nor vertical. Such line between points of two colours merely alternates between those two colours, which can be shown by reflection I think. $\endgroup$
    – abligh
    Oct 26, 2015 at 20:37
  • 1
    $\begingroup$ @MikeEarnest: No, that's okay (but note that I don't get pinged when you comment on an answer that I have no activity on). $\endgroup$
    – hmakholm left over Monica
    Oct 27, 2015 at 9:31
  • $\begingroup$ @abligh: I have added a more detailed argument. $\endgroup$
    – hmakholm left over Monica
    Oct 27, 2015 at 9:36
5
$\begingroup$

It is not possible.

Lets assume that the fleas are standing on an infinite chessboard.

First we show that it isn't possible for $A$, $B$, and $C$ to be in the same row or column:

If we assume that all rows and columns are numbered and further assume that $A$ is in an odd numbered row and column, then one of $B$ and $C$ must be in an even numbered row and odd numbered column, while the other is in an odd numbered row and even numbered column. Since a flea must always jump an even number of rows and an even number of columns it will always stay in even/odd rows/columns depending on its starting position. Therefore $A$, $B$, and $C$ can't be in the same row or column at any point in time.

Next for diagonals with any angle.

If we assume that $A$ is on a white field, then $B$ and ar on black fields. Again since a flea must always jump an even number of rows and an even number of columns it will always stay on a white/black field depending on its starting position. For any diagonal(with any angle) in a chessboard we can see, that for all fields that are exactly on the diagonal at least one of the following two statements holds true, (1)all fields in an even numbered row have the same colour and all fields in an odd numbered row have the same colour, or (2)all fields in an even numbered row have the same colour and all fields in an odd numbered row have the same colour. Therefore if $B$ and $C$ are on that diagonal then all fields on that diagonal must be black and $A$ can never land on it.

Improve this answer
$\endgroup$
6
  • 3
    $\begingroup$ A diagonal consisting of successive (2 right, 1 up) knight's moves starting at an even column will have both white and black squares in even columns. $\endgroup$
    – hmakholm left over Monica
    Oct 26, 2015 at 14:17
  • $\begingroup$ Thanks. I didn't think long enough. Fixed it now. Conclusion still holds true. $\endgroup$
    – The Dark Truth
    Oct 26, 2015 at 14:38
  • 6
    $\begingroup$ I think it would be slightly smoother to divide all (integer) points on the board into four classes according to which of their two coordinates are odd. Then no flea can ever leave the class of points it started out with. And every straight line contains points from exactly two classes (depending on which coordinates are odd in the lowest-terms representation of the line's direction). $\endgroup$
    – hmakholm left over Monica
    Oct 26, 2015 at 14:41
  • $\begingroup$ I don't understand your first assertion (maybe it's the chessboard analogy...?). Why cannot A be in (1, 1), B in (3, 1), and C in (1, 3)? Are you culling empty rows/columns or am I missing something else? $\endgroup$
    – Jacob Raihle
    Oct 26, 2015 at 16:37
  • $\begingroup$ @JacobRaihle: Imagine that you're using a coordinate system in which the initial positions of the four fleas are (0,0), (1,0), (1,1), (0,1). There is always such a system because the problem specifies that the starting positions form a square. $\endgroup$
    – hmakholm left over Monica
    Oct 26, 2015 at 16:54
3
$\begingroup$

This is an answer to the question: "Is it possible that after some time the four fleas A, B, C and D are sitting in points on the same straight line?" which is considerably simpler.

No it is not possible.

Consider the first time this would happen: by defintion being on the same line means all flea-to-flea vectors are colinear, but a jump simply means to translate by twice a flea-to-flea vector: therefore at the previous jump the flea-to-flea vectors were already colinar and the fleas were already on the same line: this contradicts the assumption that this is the first time it has happened.

Improve this answer
$\endgroup$
6
  • 5
    $\begingroup$ Your logic ignores D, which need not be colinear. $\endgroup$
    – Callidus
    Oct 26, 2015 at 12:23
  • 2
    $\begingroup$ @Callidus You're not understanding what he's said. He's doing a proof by contradiction. Since all jumps are fully reversible, if ever the fleas are all co-linear any jumps from a co-linear position will lead to another co-linear position. Therefore, if the fleas end up in a co-linear position they must have always been co-linear. So, since they didn't start in a co-linear position, it's not possible for them to reach a co-linear position. $\endgroup$
    – Shufflepants
    Oct 26, 2015 at 15:56
  • 2
    $\begingroup$ @Shufflepants: Only three of them have to be collinear to "win", not all 4. The solution is wrong. $\endgroup$
    – Deusovi ♦
    Oct 26, 2015 at 19:41
  • 1
    $\begingroup$ Oh, I misread the question and thus misinterpreted Callidus's comment. Thought the question required all 4 to be colinear. $\endgroup$
    – Shufflepants
    Oct 26, 2015 at 19:57
  • $\begingroup$ They are fleas not flies, which clearly makes all the difference :-) $\endgroup$
    – abligh
    Oct 26, 2015 at 20:35
0
$\begingroup$

Yes! It is entirely possible! But only if you allow for the use of different forms of geometry within the same problem. Then all you need to do is center their Euclidean square on the geographic North (or South) pole. If you keep the side length of the square short the fleas will appear to be in a square to the human observer. There is no hopping required. They are now on the same Elliptic line (i.e. the same Latitude).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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