Squares of Differences III: a surprising solution
October 13, 2011[See Squares of Differences I and Squares of Differences II, and apologies for the tardiness of the posting]
I’ve learned a lot about Squares of Difference in the last months. First, they’re sometimes known as Difference Boxes, or Diffy Boxes, or sometimes Ducci Sequences, or the 4 number game, and references to them are indeed available online. However, my favorite is from more recently: Josh Zucker’s wonderful description of the problem and its surprising solution on Wordplay, the New York Times Crossword Blog.
I recently worked through this problem from scratch with a student. Here’s the method we came up with, broken into stages for convenience, of getting a handle on the problem, and of showing that it’s possible to find a diffy square that never(!) resolves to zeroes:
1) First, let’s abbreviate the four numbers at the corners of the diffy square (my current name for these objects) using the notation (a,b,c,d). For example, the diffy square below could be notated (1,2,3,4). That saves us some space.
2) Notice that there are certain “moves” that don’t affect the number of moves it takes to get to all zeroes (I’ll refer to the number of moves it takes to get to all zeroes as the “length” of the diffy square). For example, you could replace (1,2,3,4) with (2,3,4,5) and all the differences would be the same at the next level, meaning the length is the same. Convince yourself that adding or subtracting any number to all four starting corners of a diffy square keeps it the same.
3) What else keeps the length of a diffy square the same? Well, we can also multiply or divide by any number. Why does this work? Try replacing (1,2,3,4) by (2,4,6,8) or, generally, (x,2x,3x,4x), for any nonzero x. When you work it through, you can see that the differences at each level down are also scaled by a factor of x. In particular, you reach zeroes at the exact same point.
4) What we have now is a new notion of “equality”–equivalence, let’s call it–that applies to groups of diffy squares. In particular, we’ll call two diffy squares “equivalent” if we can get from one to the other by a series of “moves,” where the legal moves are that you can add, subtract, multiply, or divide any nonzero real number to the four starting corner (a,b,c,d).
5) These moves give us some real freedom. In particular, it’s possibly to reduce any diffy square to the form (0,1,x,y). Convince yourself that this is true! For example, if I started with (2,5,7,11), I could subtract 2 from each corner to get (0,3,5,9), then divide by 3 to get (0,1,5/3,3). Can you show that you can do this in general?
6) Now that we have a simpler situation, we just need to ask how to pick x and y so that the diffy square one level down from (0,1,x,y) is equivalent to (0,1,x,y)! This actually isn’t too bad. Taking the differences (and making some convenient assumptions, like 2<x<y), we can calculate the next layer as (1,x-1,y-x,y). Let’s put this into our standard form by subtracting 1 to get (0,x-2,y-x-1,y-1), and then dividing by x-2 to get (0,1,(y-x-1)/(x-2),(y-1)/x-2)).
7) This is a little hideous, I know, but if we aren’t deterred by the ugliness of the expression, we can see that all we need to do is find an x and a y so that
x=(y-x-1)/(x-2) and y=(y-1)/(x-2).
These are two equations and two unknowns, so they’re theoretically (and indeed, actually) solvable. Pump the whole thing through a computer (or do a bunch of algebra and apply the cubic formula) and you get
This is a stunning find, from my point of view. It means that if we start with (0,1,2.83929,6.22226), we should get (0,1,2.83929,6.22226) again as the square inside it. This means that this is a diffy square of infinite length! (Of course, it won’t be exactly right, since we rounded the numbers off. Anybody with a computer program feel like letting me know how long it goes?)
Anyway, there’s plenty more questions to consider (like, are there other diffy squares of infinite length?), but for the moment, we have some satisfaction.