5

Squares of Differences III: a surprising solution

[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

x = 1\/3 (4+(19-3 sqrt(33))^(1\/3)+(19+3 sqrt(33))^(1\/3)) ~~ 2.83929 and y ~~ 6.22226

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.

 

 

Comments 5

  1. Joshua Zucker

    Thanks for the shout-out!

    It turns out that if you scale it to something a little different than 0,1 at the beginning, you might notice a pattern a little more easily. You get lucky if you guess 1, a, a^2, a^3, but I’m not sure how you could see that you would get lucky doing that without just trying it. You can kind of see the equation that will come out of it, scaling by a-1, maybe.

    Also when I started doing this problem I focused for a long time on only using integers. That led to a lot of LINEAR equations I could solve to generate a sequence that would last just a little longer, and once I thought about that enough, I could see where the irrational fixed point would be. So I think this is an avenue worth exploring, especially with younger students.

  2. Alexander Flint

    My son and I have been playing around with these problems in the computer since he first learned about it from Josh in his classroom. I agree with Josh that the integer version and the real number version are fundamentally distinct problems (and the integer version seems more interesting to me personally!).

    Does your real solution to the x=(y-x-1)/(x-2) and y=(y-1)/(x-2) equations imply that, at least for this approach, no integer solutions can be found that will yield an infinite length?

    Also, I’m not sure that in practice [0,1,2.83929,6.22226] should actually yield an infinite length, as with these rounded values and the float precision of Python (17 digits), one only gets 26 steps (not that many, considering the float precision) and the original numbers don’t ever really show up along the way, even in rounded form.

    Here’s the result using your starting numbers:

    [0.0, 1.0, 2.83929, 6.22226]
    [1.0, 1.83929, 3.3829700000000003, 6.22226]
    [0.8392900000000001, 1.5436800000000002, 2.83929, 5.22226]
    [0.7043900000000001, 1.29561, 2.3829700000000003, 4.38297]
    [0.5912199999999999, 1.0873600000000003, 2.0, 3.67858]
    [0.49614000000000047, 0.9126399999999997, 1.6785800000000002, 3.0873600000000003]
    [0.4164999999999992, 0.7659400000000005, 1.4087800000000001, 2.59122]
    [0.3494400000000013, 0.6428399999999996, 1.1824399999999997, 2.1747200000000007]
    [0.29339999999999833, 0.5396000000000001, 0.9922800000000009, 1.8252799999999993]
    [0.24620000000000175, 0.45268000000000086, 0.8329999999999984, 1.531880000000001]
    [0.2064799999999991, 0.38031999999999755, 0.6988800000000026, 1.2856799999999993]
    [0.17383999999999844, 0.31856000000000506, 0.5867999999999967, 1.0792000000000002]
    [0.14472000000000662, 0.2682399999999916, 0.4924000000000035, 0.9053600000000017]
    [0.12351999999998498, 0.2241600000000119, 0.4129599999999982, 0.7606399999999951]
    [0.10064000000002693, 0.1887999999999863, 0.3476799999999969, 0.6371200000000101]
    [0.08815999999995938, 0.15888000000001057, 0.28944000000001324, 0.5364799999999832]
    [0.07072000000005119, 0.13056000000000267, 0.24703999999996995, 0.4483200000000238]
    [0.05983999999995149, 0.11647999999996728, 0.20128000000005386, 0.3775999999999726]
    [0.05664000000001579, 0.08480000000008658, 0.17631999999991876, 0.31776000000002114]
    [0.028160000000070795, 0.09151999999983218, 0.14144000000010237, 0.26112000000000535]
    [0.06335999999976138, 0.04992000000027019, 0.11967999999990298, 0.23295999999993455]
    [0.013439999999491192, 0.06975999999963278, 0.11328000000003158, 0.16960000000017317]
    [0.05632000000014159, 0.043520000000398795, 0.05632000000014159, 0.15616000000068198]
    [0.012799999999742795, 0.012799999999742795, 0.09984000000054039, 0.09984000000054039]
    [0.0, 0.08704000000079759, 0.0, 0.08704000000079759]
    [0.08704000000079759, 0.08704000000079759, 0.08704000000079759, 0.08704000000079759]
    [0.0, 0.0, 0.0, 0.0]
    Total iterations = 26

    1. Post
      Author
      Dan

      Very cool to try them out…

      “Does your real solution to the x=(y-x-1)/(x-2) and y=(y-1)/(x-2) equations imply that, at least for this approach, no integer solutions can be found that will yield an infinite length?”

      I believe the answer to this question is yes. In fact, I think it’s possible to prove that any integer collection of numbers (or rational collection, equivalently) must terminate after a finite number of steps.

      I rounded those numbers off to 4 decimal places. What if you solve those equations to 17 digits and try those numbers?

      The fact that the original numbers never show up along the way is one of the subtleties of this method: the solutions (if you use the real numbers) are in the same family, but are not visibly the same. The connection is very well hidden.

      1. Paul G

        You can run this script at https://repl.it/languages/python to play around with your own numbers or variations.

        ———
        a = 0
        b = 1
        c = 2.83929
        d = 6.22226
        print “%s %s %s %s” % (a, b, c, d)

        while a != 0 or b != 0 or c != 0 or d != 0:

        newa = abs(b – a)
        newb = abs(c – b)
        newc = abs(d – c)
        newd = abs(a – d)

        a = newa
        b = newb
        c = newc
        d = newd

        print “%s %s %s %s” % (a, b, c, d)

  3. Chris Guenther

    Here’s my code on repl.it. I modified the above code, but put in the closed form of the cubic solution, which I found by solving d^3-7d^2+5*d-1=0 on Wolfram Alpha. Using Python’s precision, it runs through 66 iterations. I also scale each square so it’s of the form (0, 1, x, y), and you can see it slowly drift and then take off.

    n = 1

    a = 0
    b = 1
    #c = 2.8 # 2.83929
    #d = 6.2 # 6.22226
    d = ((3916917-59049*(33)**(1/2.0))**(1/3.0) + 27*(199+3*(33)**(1/2.0))**(1/3.0))/81.0+7/3.0
    c = (3*d-1)/d
    print “(%2d): %s %s %s %s” % (n, a, b, c, d)

    while a != 0 or b != 0 or c != 0 or d != 0:

    n = n + 1

    newa = abs(b – a)
    newb = abs(c – b)
    newc = abs(d – c)
    newd = abs(a – d)

    oldc = c
    oldd = d

    #a = newa
    #b = newb
    #c = newc
    #d = newd
    a = 0
    b = 1
    c = (newc-newa)/(newb-newa)
    d = (newd-newa)/(newb-newa)

    print “(%2d): %s %s %s %s” % (n, a, b, c, d)

Leave a Reply to Dan Cancel reply

Your email address will not be published. Required fields are marked *