Take Away Triangles

Matt Parker calls his latest puzzle Take Away Triangles, though really it has nothing to do with geometry; it’s purely about numbers.

Consider a triple of integers (Parker doesn’t say they have to be positive, but he doesn’t say they don’t): (a, b, c). Without loss of generality, herein I’m going to require all such triples to be in nondecreasing order: a \le b \le c. Now make a new triple out of it using the three differences b-a, c-b, and c-a. These all are nonnegative, and of them c-a is the largest (in fact c-a = (b-a) + (c-b)), so the new triple is either (b-a, c-b, c-a) or (c-b, b-a, c-a). We’ll call this new triple the successor of the first, and the first is a predecessor of the second. Now of course we can find the successor of the successor, and the successor of the successor of the successor, and so on.

For instance, starting with (5, 7, 12), we get as its successors (2, 5, 7), then (2, 3, 5), then (1, 2, 3), and so on.

The basic puzzle is this: Find a triple whose members do not sum to 14, whose successor does sum to 14, as do all the successors in the chain after that.

Let’s approach this in three steps:

  1. Find all triples that do sum to 14 whose successor also sums to 14
  2. Identify all whose second and following successors also sum to 14
  3. Find all predecessors of those triples

All right. We want to find a triple (a, b, c) such that a+b+c = 2s (s is 7, but let’s keep it symbolic for now, and you’ll see why I put a factor of 2 there). Its successor has members b-a, c-b, and c-a, and we want them to sum to 2s too: b-a+c-b+c-a = 2c-2a = 2s, so c-a = s or a = c-s. We have b = 2s - a - c = 2s-(c-s)-c = 3s-2c. So triples of the form (c-s, 3s-2c, c) will work.

What values can we use for c? We need a \le b so c-s \le 3s-2c \implies c \le 4s/3, and b \le c so 3s-2c \le c \implies c \ge s. For s=7 that means 7 \le c \le 9. The only triples that sum to 14 whose successors also sum to 14 are:

  • (0, 7, 7), whose successor is (0, 7, 7)
  • (1, 5, 8), whose successor is (3, 4, 7)
  • (2, 3, 9), whose successor is (1, 6, 7)

Next step is easy. The second and third of these have second successors which do not sum to 14. The first is its own successor, and therefore all of its successors: It and all its successors sum to 14, and that’s the only triple with that property.

Now we just need a predecessor for (0, 7, 7), or better yet, all predecessors. Any that don’t sum to 14 will answer the puzzle. So we want (e, f, g) such that either

  • f-e = 0
  • g-f = 7 and
  • g-e = 7

or

  • f-e = 7
  • g-f = 0 and
  • g-e = 7

In the first case, e=f and f = g-7 so we have predecessors of the form (g-7, g-7, g). The second case works out to (g-7, g, g). So predecessors of the first kind include (-2, -2, 5), (-1, -1, 6), (0, 0, 7), (1, 1, 8), and (2, 2, 9). Predecessors of the second kind include (-2, 5, 5), (-1, 6, 6), (0, 7, 7), (1, 8, 8), and (2, 9, 9). Only (0, 7, 7) sums to 14. Any other triple of one of these forms solves the puzzle.

Now let’s consider some wider aspects.

First, given a triple (a, b, c) with a, b, c \ge 0, what are its predecessors? We want (e, f, g) such that either

  • f-e = a
  • g-f = b and
  • g-e = c

or

  • g-f = a
  • f-e = b and
  • g-e = c

In either case, a+b must equal c, so only triples for which that is true have predecessors. Then in the first case: f = a+e, g = b+f = a+b+e = c+e, and e is unconstrained, so the predecessors are (e, a+e, c+e) for all e. In the second case we get (e, b+e, c+e).

Second, given a starting triple, what’s the behavior of its successors? Can they go indefinitely without repeating? If they do repeat, what’s the period of the repetition?

A triple that is the successor of another triple must be of the form (x, y, x+y). The successor of that successor must be either ((y-x), (x+y)-y, (x+y)-x) or ((x+y)-y, (y-x), (x+y)-x). But these simplify to (y-x, x, y) or (x, y-x, y). In either case two of the second successor’s members are the first two members of the first successor. In particular, the third member of the second successor is the second member of the first successor.

What that means is the chain cannot continue indefinitely without repeating, because the third member cannot increase (except in the successor to the starting triple, and that only if the starting triple’s first member is negative). It’s bounded from above in all successors by its value in the starting triple’s successor and from below by zero, and the first and second members must be no larger and nonnegative, so there is only a finite number of triples that can occur in the successor chain, and eventually it must repeat.

We’ve seen the repetition period can be 1. If that is the case — if we reach a triple (x, y, x+y) which is its own successor — then the third member of its successor, (x+y)-x = y, must be equal to x+y implying x = 0. So the only self-succeeding triples are of the form (0, y, y).

Can the period be longer? The largest member cannot increase, so if it is x+y in the first triple in the repeating cycle and is to be x+y in some later triple in the cycle, it must be x+y in every triple in the cycle. In particular it must be x+y in the successor to the first triple of the cycle, so again x=0, the cycle’s first triple must be (0, y, y), and that is self-succeeding. So the period must be 1.

For any starting triple, then, the chain of successors after a finite number of steps reaches a triple of the form (0, y, y) and repeats that triple from there on.

2 thoughts on “Take Away Triangles

  1. We can define, I suppose, a similar successor function also for other n-tuples, although for n > 3 the output will be an m-tuple with m > n (specifically △(n-1) with △ being the triangle numbers function), which makes any hunting for further interesting cycles impossible.

    A follow-up pass could be to define “collapsed successors”, based on unordered sets rather than ordered n-tuples, so that {a(1), a(2)… a(n)} gives the set of numbers |a(i)-a(j)| with i, j ≤ n, i ≠ j (that is, we remove duplicates) and this set does not have to be larger than the starting set. Unfortunately in this case loops cannot exist either. The largest member of a set can again only either remain or decrease under successor; it can only remain if the set contains 0 as a member; but since sets cannot have repeated members, no set has a set containing 0 as its successor.

    Another way to make room for the possibility of cycles would be if we operated “in a circle”, taking (a, b, c … x, y) to (b-a, c-b, … y-x, y-a) but ignoring “cross-differences” such as c-a, … x-a. That is, take all successive elements’ differences, with the first element taken to be the successive element of the last one.

    In this case we do then find cycles: e.g. among 4-tuples, (0, 2, 2, 4) would prove to form a cycle of period 1. There still cannot be 4-tuple cycles of period > 1 (proof left as excercise). Starting with 5-tuples we do find larger periods though, e.g. (0, n, n, 3n, 5n) will oscillate with (0, n, 2n, 2n, 5n).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s