Frogs In A Line

Time to put up the solution to the frogs puzzle from last time.

First of all, let us analyse what sort of move a frog can make, since we are trying to prove that the frogs cannot reach some configuration it makes sense to find some conserved quantity. First let us assume that the frogs start out on the locations [0,0], [0,1], [1,0], [1,1], that is the square they begin on.

Suppose we have a frog at [x1,y1] and another at [x2,y2] and frog 1 jumps frog 2. He then moves to [x1+2(x2-x1),y1+2(y2-y1)], that is, his position increases by double the distance between 1 and 2. First of all, this shows that if they start on integer coordinates, they must remain in integer coordinates, they cannot leave the integer grid through any moves. Anyway, our new frog position is [2x2-x1,2y2-y1]. Specifically, if the x location was even before the jump, it remains even after the jump, and if it was odd, it remains so, similarily for the y coordinate. So we have a conserved quantity for our frog motions. In particular since they start out [even,even], [even,odd], [odd,even], [odd,odd], they will remain so forever. So now we know that it is impossible for two frogs to ever be on the same location, since our frogs all have different parities. This also quickly shows we cannot ever have three frogs on a line that is lined up along our coordinate grid (the lines x=constant or y=constant), but it is less obvious that you cannot have three frogs on an angled line (ax+by=constant), I will show that now.

So, suppose you were to reach some configuration where the frogs are all on a line (at different places on the line of course, we know they cannot share a location). That line goes through infinitely many points on our grid, all spaced out a distance d apart. Identify the middle frog, and the other two frogs are distances u and v away from it. We can see that u and v must both be positive integer multiples of d, and if u=v we can have one frog jump to get two frogs on the same location, so u cannot equal v. Suppose u is less than v (if not, rename u and v), have the frog that is distance u away jump over the middle frog. The jumping frog will become the new middle frog and the distances are now u and v-u. Call the smaller of these two u' and the larger one v'. We can see that u'+v'=v, so u'+v' is smaller than u+v. If u' does not equal v', then repeat the process, have the frog u' away jump the middle frog. We will keep repeating this process, and each time we do, we make u and v smaller numbers. But they are always integer multiples of d so eventually we will get to a point where two frogs must share a location (it cannot take more than the initial (u+v)/d steps to do this). At this point we have a contradiction.

I suppose one could also analyse ax+by=c for values of x and y being even and odd and show that you won't have three frogs on a line without breaking the parity rule, but then you have to go through all sorts of arguments about a, b, and c being integers first. Its not really any harder that way, but I find the argument of the previous paragraph more compelling.

If you want a follow up problem to this, it was given in the comments last time, show that you cannot ever have the four frogs arrange themselves into a larger square. The solution was also given in the comments, so I won't go over it.

1 comment:

Ben Williams said...

This solution, in fancy language, reduces the problem from the lattice Z^2 to the vector space F^2 where F is Z/2. That is, instead of thinking about (a,b) where a, b are integers, we think of a and b as simply being even or odd, or 1 or 0. From now on, I'll just write (1,0) etc to indicate a point in F^2.

The solution observes that the positions of the frogs (reduced to F^2) do not change at all when they 'jump'.

It is the case that F is a field, which has the implication that all lines in F^2 are equivalent. That is, for any two lines L, M in F^2 (and there are only 6, but the argument works for K^n where K is any field and n is any integer) there is a symmetry of F^2 taking L to M. To see this, it suffices to show that there is a symmetry taking a given line, L, to a standard line such as x=0. A translation can be used to ensure L passes through the origin. Then L takes the form t(a,b) where t is a parameter and (a,b) is a nonzero vector. Because (a,b) is nonzero, we can use it as the first column of some invertible matrix, A, and then we find that A^(-1) will translate our line L to the line x=0.

Notably, every line in F^2 has the same number of points on it as x=0 does, which is 2: (0,0), (0,1). This means that at no stage can three frogs lie on a line in Z^2, since we could reduce to F^2 and discover three frogs, each at a different point of F^2, lying on a line in F^2, which is a contradiction.

This line of argumentation gets you out of discussing cases (at the considerable expense of having to have already developed a theory of affine symmetries of general vector spaces).

This question is interesting because it starts to raise questions about how one should even go about defining 'a line' in general. Clearly we don't want something stupid like 'all multiples of (2,2)' to be a line in Z^2.