4

You are given four points (on a Euclidian plane) that make up the corners of a square. You may change the positions of the points by a sequence of moves. Each move changes the position of one point, say p, to a new location, say p', by "skipping over" one of the other 3 points. More precisely, p skips over a point q if it is moved to the diametrically opposed side of q. In other words, a move from p to p' is allowed if there exists a point q such that $q = (p + p') / 2$.

Find a sequence of moves that results in a larger square. Or, if no such sequence is possible, give a proof of why it isn't possible. (The new square need not be oriented the same way as the original square. For example, the larger square may be turned 45 degrees from the original, and the larger square may have the points in a different order from in the original square.)

I've tried many different combinations and still haven't gotten anything more than 3 points in the right position and one point completely off. Is this possible?

narcissa
  • 771
  • For the record, I previously claimed that the area of the polygon doesn't change during a move. This is incorrect, as coffeemath pointed out with a helpful example. My reasoning was that for any move, the area can be decomposed into two triangles, whose areas don't change in magnitude. In retrospect the mistake was obvious: one oriented triangle can change orientation while the other doesn't. I missed the error due to some diagrams that I had misinterpreted. Unfortunately, I haven't been able to find a true invariant to replace the area. I'd be very interested in such a solution! – Chris Culter Aug 12 '13 at 05:34
  • Chris: I found another example for which both quadrilaterals are convex: $P=(0,0),(2,0),(3,2),(1,1)$ with area $\frac52$ and $Q=(2,0),(4,0),(3,2),(1,1)$ with area $\frac72$, and $Q$ is obtained from $P$ by jumping $(0,0)$ over $(2,0)$ to give the vertex $(4,0)$ of $Q$. So nonconvex quads aren't the only offenders. – coffeemath Aug 12 '13 at 06:01

1 Answers1

4

If this were possible, the sequence of moves from the starting square ABCD to the final square EFGH could be reversed, giving a move sequence from a larger to a smaller square. If a coordinate system is set up based on the larger square, making it correspond to the points $(0,0),(0,1),(1,1),(1,0)$, then all moves made starting with the larger square will take a point with integer coordinates to another point with integer coordinates. But this means one cannot end up with the smaller square ABCD desired, since the smallest square in the new coordinate system with integer coordinate vertices is a unit square in that system.

coffeemath
  • 29,884
  • 2
  • 31
  • 52
  • On further thought, you had the right invariant all along! Since any move can be reversed, the lattice generated by the points is fixed. No sequence of moves can produce a larger square, since it generates a different lattice. – Chris Culter Aug 12 '13 at 15:01
  • @ChrisCulter Ah. Now I see (I think). If one arrived at a larger square, further moves would stay in its lattice. Then the moves could not be reversed. I guess its another slant on the big-small square relation via move sequences... – coffeemath Aug 12 '13 at 15:35
  • That's not quite what I meant... We don't have to wait until we reach a square to apply the argument. By "generate a lattice", I mean that for any shape at all, we can always consider the subset of the plane that consists of integer linear combinations of the given points, where the coefficients sum to 1. This set is not always a discrete lattice, but in our case, starting from a square, it is. If one set of points generates a lattice, then a move stays within the lattice, so the new points generate a sublattice. But the reversible move argument shows that it's the same lattice! – Chris Culter Aug 12 '13 at 15:52
  • @ChrisCulter Since there are four points, did you mean to say the coefficients sum to 4 (and are nonnegative integers)? – coffeemath Aug 12 '13 at 16:10
  • 1
    Integers summing to 1 is correct. It's the affine hull with integer coefficients, and linear combinations in points in affine space make sense only when the coefficients sum to 1. Or, if you prefer, we can choose one of the points to be the origin, so that the plane becomes an additive group. Then the lattice generated by the points is the same as the subgroup generated by the points. – Chris Culter Aug 12 '13 at 16:48