Source

I got this problem from Rustan Leino, who got it from Radu Grigore.

I solved it and wrote up my solution.

Problem

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 three 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.)

Solution
Reveal

Here's a proof that it's impossible. Suppose it is possible, and there's a
legal sequence of moves that results in a larger square. Every legal move
can be undone, and this undoing is also a legal move since it's just
skipping the same point over the same other point again. Thus, the entire
procedure can be undone by undoing its moves in reverse, and this undoing is
also a legal sequence of moves. Thus, there must be a sequence of legal
moves that produces a *smaller* square.

Now, start with points at positions $(0, 0), (1, 0), (0, 1), (1, 1)$ and apply the square-reducing procedure. Each step of this procedure chooses two point positions $p$ and $q$ and replaces $p$ with $p' = 2q - p.$ Thus, each step preserves the invariant that all coordinates of all points are integers. So, we wind up with a square whose corners have integer coordinates but which has side smaller than 1. In particular, we have two points that share a square edge whose distance to each other is between 0 and 1 even though both have integer coordinates. This is impossible.