April 28–May 4, 2009
Problem
Draw a square, and label the corners with any four nonnegative integers. At the midpoint of each side, write the difference of the two adjacent numbes, subtracting the smaller one from the larger. This produces a list of four new numbers, written on a smaller square. Repeat this process.
For example, starting with the numbers 2, 3, 5, 6, we generate the following squares:
It's not really necessaary to draw the squares; we can just write the iterations as a table. Given the row (a, b, c, d), the next row is (|a-b|, |b-c|, |c-d|, |d-a|):
2 3 5 6 1 2 1 4 1 1 3 3 0 2 0 2 2 2 2 2 0 0 0 0
Notice that we reached a row of zeros (equivalently, a square with all its vertices labeled 0) in 6 steps.
The problem: Prove that the process always reaches (0, 0, 0, 0) eventually.
(This is a tricky problem, but there are lots of other interesting questions to think about along the way: how can you pick starting numbers so that many steps are needed to get to (0, 0, 0, 0)? Could you pick starting values so it takes 100 steps? What happens when non-integer values are used—how long does the sequence (0, 1, 6, π) take? What happens if we start with pentagons or hexagons instead of squares?)
Solution
List of solvers
Colin Meyer (undergrad, Berkeley); Koopa Koo (graduate); Peiyush Jain, Lloyd Sakazaki, Gourav Chanda, Hardik Bati, Justin Shih, David Kaplan (outside).
Peiyush Jain wins the prize!