Diffygons—Solutions

Fall 2019 ARML Power Contest

Problem 1. Simply apply the difference operation and compute the results:
(a) ∆(9, 17, 31, 57) = (8, 14, 26, 48), ∆2 (9, 17, 31, 57) = (6, 12, 22, 40), ∆3 (9, 17, 31, 57) =
(6, 10, 18, 34), and finally ∆4 (9, 17, 31, 57) = (4, 8, 16, 28) .
(b) Continuing, ∆5 (9, 17, 31, 57) = (4, 8, 12, 24), ∆6 (9, 17, 31, 57) = (4, 4, 12, 20), ∆7 (9, 17, 31, 57) =
(0, 8, 8, 16), ∆8 (9, 17, 31, 57) = (8, 0, 8, 16), ∆9 (9, 17, 31, 57) = (8, 8, 8, 8) and finally ∆10 (9, 17, 31, 57) =
(0, 0, 0, 0) so the longevity is 10 .

Problem 2.
(a) ∆(4, 2, 8, 3, 6) = (2, 6, 5, 3, 2) .
(b) 3 · A + 7 = (12, 6, 24, 9, 18) + 7 = (19, 13, 31, 16, 25) .
(c) ∆(19, 13, 31, 16, 25) = (6, 18, 15, 9, 6) .

Problem 3. These follow easily from properties of arithmetic and absolute value.
(a) Given any two real numbers a and b, note that (a + c) − (b + c) = a + c + b − c = a − b
and likewise the absolute values of both sides are equal. Apply this to each slot of ∆A.
(b) Given any two real numbers a and b, note that ka − kb = k(a − b) and taking absolute
values yields |ka − kb| = |k(a − b)| = |k||a − b|. Thus, each slot of ∆(k · A) is simply |k|
times the corresponding entry of ∆A, which is the definition of |k| · ∆A.

Problem 4. Let c = min(a1 , a2 , . . . , an ) and let B = A + (−c). Since c ≤ ak for any k,

ak − c ≥ 0 and since c = amin for whichever subscript(s) correspond to the smallest a, there
is at least one zero among the entries of B. So B is an n-tuple whose minimum element is
0, and by problem 3(a) ∆B = ∆A.

Problem 5.
(a) Note that adding a constant to all numbers in a list increases or decreases both the
minimum and the maximum number in the list by the same amount. Thus, the argument
from 3(a) applies to the range.
(b) Similarly, the argument from 3(b) applies here, since if k is positive both the minimum
and maximum are multiplied by the same amount (which then factors out of the difference).
If k is negative, the role of the maximum and minimum are interchanged, but then −k = |k|
is factored out of the difference. If k = 0 then all products become zero as does the range.
(c) Use part (a) and problem 4 to obtain from A another n-tuple B whose minimum
element is zero and whose range is the same as that of A. The maximum element of B must
be r(A). But since all the elements of B are nonnegative, the minimum elements of ∆B is

1
nonnegative and the maximum element of ∆B is at most the maximum element of B. Thus,
r(∆A) = r(∆B) ≤ r(A).

Problem 6.√ To keep track of the relative sizes of the numbers, approximate√ π ≈ 3.1,
e ≈ 2.7, and 2 ≈ 1.4. So the results of recursively applying ∆ to (π, e, 4, 2) are:
√ √ √
∆(π, e, 4, 2) = (π − e, 4 − e, 4 − 2, π − 2)
√ √ √
∆2 (π, e, 4, 2) = (4 − π, e − 2, 4 − π, e − 2)
√ √
∆3 (π, e, 4, 2) = (a, a, a, a), where a = e + π − 2 − 4
√
∆4 (π, e, 4, 2) = (0, 0, 0, 0)

Problem 7. The table below lists every possible combination of even (e) and odd (o) entries
a diffy box could have, and what combination it will have after ∆ is applied. Naturally, o − e
and e − o both lead to o while e − e and o − o lead to e when computing ∆. Of course,
the table is quite redundant (for example, (e, o, o, o) and (o, e, o, o) are just rotations of each
other.
A ∆A ∆2 A ∆3 A ∆4 A
(o, o, o, o) (e, e, e, e) (e, e, e, e) (e, e, e, e) (e, e, e, e)
(o, o, o, e) (e, e, o, o) (e, o, e, o) (o, o, o, o) (e, e, e, e)
(o, o, e, o) (e, o, o, e) (o, e, o, e) (o, o, o, o) (e, e, e, e)
(o, o, e, e) (e, o, e, o) (o, o, o, o) (e, e, e, e) (e, e, e, e)
(o, e, o, o) (o, o, e, e) (e, o, e, o) (o, o, o, o) (e, e, e, e)
(o, e, o, e) (o, o, o, o) (e, e, e, e) (e, e, e, e) (e, e, e, e)
(o, e, e, o) (o, e, o, e) (o, o, o, o) (e, e, e, e) (e, e, e, e)
(o, e, e, e) (o, e, e, o) (o, e, o, e) (o, o, o, o) (e, e, e, e)
(e, o, o, o) (o, e, e, o) (o, e, o, e) (o, o, o, o) (e, e, e, e)
(e, o, o, e) (o, e, o, e) (o, o, o, o) (e, e, e, e) (e, e, e, e)
(e, o, e, o) (o, o, o, o) (e, e, e, e) (e, e, e, e) (e, e, e, e)
(e, o, e, e) (o, o, e, e) (e, o, e, o) (o, o, o, o) (e, e, e, e)
(e, e, o, o) (e, o, e, o) (o, o, o, o) (e, e, e, e) (e, e, e, e)
(e, e, o, e) (e, o, o, e) (o, e, o, e) (o, o, o, o) (e, e, e, e)
(e, e, e, o) (e, e, o, o) (e, o, e, o) (o, o, o, o) (e, e, e, e)
(e, e, e, e) (e, e, e, e) (e, e, e, e) (e, e, e, e) (e, e, e, e)
Since the entry in the ∆4 column is alwaye (e, e, e, e) all diffy boxes containing only integers
yield all even integers after four applications of ∆.

Problem 8. The idea of the proof is that applying ∆ four times, as in the previous problem,
leads to all even entries, so 2 can be factored out of the diffy box, and also out of the range.
But the range stays the same or shrinks when applying ∆. Since the range is finite, factors
of two cannot continue to be removed forever!
Specifically, let n be an integer so that 2n > r(A). Define A0 = A. Since ∆4 A0 consists
of all even terms, define A1 so that ∆4 A0 = 2 · A1 . Recusively define Ak to be such that
∆4 Ak−1 = 2 · Ak . Inductively, ∆4k A0 = 2k · Ak .

2
 Now consider the range: 2n > r(A) = r(A0 ) ≥ r(∆4n A0 ) = r(2n An ) = 2n r(An ), the
last equality courtesy of problem 5(b). Thus, r(An ) < 1 but since all numbers involved are
integers the only way this can happen is if r(An ) = 0, meaning all entires of An are equal.
Then ∆An = (0, 0, 0, 0). Conclusion: ∆4n+1 A = (0, 0, 0, 0).

Problem 9. This will be a brute force computation. Note that the Triboncaii numbers
are increasing for indices larger than 1. Then ∆(tn , tn+1 , tn+2 , tn+3 ) = (tn+1 − tn , tn+2 −
tn+1 , tn+3 − tn+2 , tn+3 − tn ). Applying the recursive definition tn = tn−1 + tn−2 + tn−3 to these
combinations yields (tn−1 + tn−2 , tn + tn−1 , tn+1 + tn , tn+2 + tn+1 ). Note that since indices are
as small as n − 2 the assumption that n ≥ 2 was necessary.
Now apply ∆ again: ∆2 Tn = (tn − tn−2 , tn+1 − tn−1 , tn+2 − tn , tn+2 + tn+1 − tn−1 − tn−2 ).
The last entry may be simplified, by adding and subtracting tn :

tn+2 + tn+1 − tn−1 − tn−2 = tn+2 + tn+1 + tn − tn − tn−1 − tn−2

= tn+2 + tn

by noting that tn+1 − tn − tn−1 − tn−2 = 0. Thus ∆2 Tn = (tn − tn−2 , tn+1 − tn−1 , tn+2 −
tn , tn+2 + tn ).
It will simplify the next step to use the recurrence relation to replace tn+1 − tn−1 with its
equivalent tn + tn−2 and tn+2 − tn with tn+1 + tn−1 . Thus ∆2 Tn = (tn − tn−2 , tn + tn−2 , tn+1 +
tn−1 , tn+2 + tn ).
Apply ∆ one more time to produce ∆3 Tn = (2tn−2 , tn+1 − tn − tn−2 + tn−1 , tn+2 − tn+1 −
tn−1 +tn , tn+2 +tn−2 ). The second and third entries can be simplified by replacing the highest
index term using the recurrence relation and simplifying, yielding 2tn−1 and 2tn respectively.
The final entry is simplified as tn+2 + tn−2 = tn+1 + tn + tn−1 + tn−2 = tn+1 + tn+1 = 2tn+1 ,
replacing the top index term and then grouping the three lowest-index terms together in the
result. The final result is ∆3 Tn = (2tn−2 , 2tn−1 , 2tn , 2tn+1 ) = 2 · Tn−2 as desired.

Problem 10. Compute the longevity of T0 and T1 (each arrow represents applying ∆):
T0 = (0, 0, 1, 1) −→ (0, 1, 0, 1) −→ (1, 1, 1, 1) −→ (0, 0, 0, 0) and T1 = (0, 1, 1, 2) −→
(1, 0, 1, 2), −→ (1, 1, 1, 1) −→ (0, 0, 0, 0). So both these boxes have longevity 3.
Now if n is even, say n = 2k, then applying the results of problems 3 and 9 shows that
∆ Tn = 2k · T0 and then three more applications of ∆ yields all zeroes. So the longevity is
3k

3k + 3.
In case n is odd, say n = 2k + 1, the result is the ∆3k Tn = 2k T1 and, again, three more
applications yields all zeroes.
Combining these yields the formula 3n/2 + 3 for n even and 3(n − 1)/2 + 3 for n odd.
These can be combined in a formula such as 3b n2 c + 3.

Problem 11. Once again, simply compute ∆(1, t, t2 , t3 ) = (t − 1, t2 − t, t3 − t2 , t3 − 1) =

(t − 1, t(t − 1), t2 (t − 1), (t2 + t + 1)(t − 1)) = (t − 1) · (1, t, t2 , t2 + t + 1). Of course, since
t3 − t2 − t − 1 = 0 the last term in the diffy box can be replaced by t3 which is the desired
result.

Problem 12. Of course, an n-tuple that is all zeroes has a longevity of zero, but no other

3
n-tuple has longevity zero.
(a) The longevity will be one if and only if applying ∆ yields all zeroes, which occurs if and
only if all the numbers in the n-tuple are the same.
(b) If the longevity of A = (a1 , a2 , . . . , an ) is 2, then ∆A has longevity 1, so by part (a)
must have the form (c, c, . . . , c) for some non-zero c. Thus |a2 − a1 | = c or a2 − a1 = ±c.
Similarly, a3 − a2 = ±c, and so forth until an − an−1 = ±c and a1 − an = ±c.
Add all n of these equations. On the left-hand side, each ai occurs once with a plus and
once with a minus, so the left-hand side is zero. On the right-hand side there will be k +’s
and n − k −’s. So the result of adding the ±c’s on the right-hand side is (2k − n)c. But c is
not zero, and since n is odd 2k − n cannot be zero either. Thus the right-hand side cannot
equal zero, forcing a contradiction. So no odd-length n-tuple can have longevity equal to 2.
Of course, since the longevity of ∆A is one less than the longevity of A, no odd-length
n-tuple can have longevity longer than 2 either.

Problem 13. To make the following simpler, consider any diffy box where two non-
adjacent elements are equal, which can be rotated to look like (a, b, a, c). Start applying ∆:
∆(a, b, a, c) = (x, x, y, y) where x = |b − a| and y = |c − a|. Then ∆2 (a, b, a, c) = (0, z, 0, z)
where z = |x − y|. Of course, ∆3 (a, b, a, c) = (z, z, z, z) and ∆4 (a, b, a, c) = (0, 0, 0, 0). So if
two non-adjacent elements are equal, the longevity is at most four.
From earlier work, only (0, 0, 0, 0 has longevity zero, and only (c, c, c, c) with c 6= 0 has
longevity 1. All other diffy boxes must have larger longevity. Thus problems 3 and 4 apply
without changing the longevity. The diffy box can be rotated so that its minimum element
comes first. The results of problems 3 and 4 can then be applied so that this first entry can
be assumed to be zero and the first non-zero entry can be assumed to be 1.
The possibilities for diffy boxes are thus scaled, translated, and/or rotated versions of
one of the following cases:

(0, 0, 0, 1) This category includes all boxes where the smallest number occurs three times.
Applying ∆ yields (0, 0, 0, 1) −→ (0, 0, 1, 1) −→ (0, 1, 0, 1) −→ (1, 1, 1, 1) −→ (0, 0, 0, 0)
so if three of the entries are equal the longevity is four.

(0, 0, 1, 1) From the previous case, diffy boxes with this pattern are seen to have longevity 3.

(0, 0, 1, a) If a > 1 then this case yields (0, 0, 1, a) −→ (0, 1, a − 1, a) −→ (1, |(2 − a)|, 1, a).
If a < 1 then this case yields (0, 0, 1, a) −→ (0, 1, 1 − a, a) −→ (1, a, |(2a − 1)|, a). For
both possibilities, two applications of ∆ led to a box with equal non-adjacent terms,
which has already been shown to take at most four more steps to reach all zeroes.

(0, 1, 0, a) For any a the longevity is at most four because of the two non-adjacent equal
entries.

(0, 1, 1, 0) Has longevity 3 from the second case.

(0, 1, 1, 1) Applying ∆ yields (1, 0, 0, 1) which is again the second case, so diffy boxes where
the largest number occurs three times have longevity four.

4
(0, 1, 1, a) The evolution is (0, 1, 1, a) −→ (1, 0, |a − 1|, a) −→ (1, |a − 1|, x, |a − 1|) where the
value of x doesn’t matter because two non-adjacent entries are equal, so this case has
longevity at most six.

(0, 1, a, 0) This is rotated from (0, 0, 1, a) above.

(0, 1, a, 1) This has two non-adjacent equal entries.

(0, 1, a, a) This evolves as (0, 1, a, a) −→ (1, |a − 1|, 0, a) −→ (x, |a − 1|, a, |a − 1|) so this case
has longevity at most six, regardless of the value of x.

(0, 1, a, b) Since the terms aren’t allowed to increase, either a < 1 or b < a. But not both!
Otherwise the terms would strictly increase if we went around the box in the other
direction.

In the case a < 1, the evolution will be (0, 1, a, b) −→ (1, 1 − a, b − a, b) −→ (a, |b −

1|, a, |b − 1|) which lasts at most two more steps. If a > 1 and a > b then (0, 1, a, b) −→
(1, a − 1, a − b, b) −→ (|a − 2|, |b − 1|, |a − 2b|, |b − 1|) which lasts at most four more steps.
Since all possiblities have now been accounted for, the conclusion that any box where the
terms do not strictly increase must have longevity at most six is proven.