Associated Topics || Dr. Math Home || Search Dr. Math

### Subtraction Puzzle

```Date: 08/18/2002 at 17:55:47
From: Eric
Subject: Subtraction puzzle

With any four whole numbers, (in any order) follow these instructions:

For numbers A, B, C, and D, subtract A from B, (or vice-versa; you
must be left with a whole number, not a negative one). Repeat with
B and C, C and D, and D and A. This leaves you with 4 new whole
numbers (they must be in the order I used). Repeat the pattern with
these. After about 6 steps, you will ALWAYS end up with 0000.

Example: 13, 104, 9, 0
91, 95, 9, 13
4, 86, 4, 78
82, 82, 74, 74
0, 8, 0, 8
8, 8, 8, 8
0, 0, 0, 0

It took 7 steps here to get to 0000. The puzzle is to get as many
steps as possible (at least 13).
```

```
Date: 08/27/2002 at 08:40:36
From: Doctor Peterson
Subject: Re: Subtraction puzzle

Hi, Eric.

This is a fascinating problem, and I've been thinking about it off
and on since I read your question. I'd like to let you know some of
what I've found on my own and in searching for information on it.
Most likely you were expected just to try lots of numbers, and maybe
see a few patterns that might help you lengthen a sequence. I'm
looking not only for those patterns, but for a general rule that will
let me determine whether you can find a set of numbers for which the
sequence will be as long as you like. In fact, I haven't tried to go
beyond the 11 steps I found in one experimental sequence.

First, after playing with the problem on my own, I went to the web to
find whatever information I could on it. One page that proves that
you will always get to zero eventually (and discusses some of the

Integer Iterations on a Circle - Cut the Knot, Alexander Bogomolny
http://www.cut-the-knot.org/SimpleGames/IntIter.shtml

Another page that discusses this, and gives some additional
references for it, is

cs150 Project 1 - A Parlor Trick, Gary R. Greenfield
http://www.mathcs.richmond.edu/~grg5l/cs150/Proj1.html

Neither of these, however, touches on our goal of finding very long
sequences. (A couple of other pages I found just ask that question,
without giving any hints as to how we can do it.)

Now I'll go through a few of the techniques I've been using. The main
thing I worked on was trying to work backward, adding more steps to
the top (beginning) of a known sequence to lengthen it. That led to
several discoveries.

First, we have the question of parity (even and odd numbers),
discussed in the Cut-the-knot page above. Notice that when you take
differences, the difference between two odd numbers or two even
numbers is always even, and the difference between an odd and an even
number is always odd. So if we consider the 16 possible patterns of
even and odd numbers, and look at the pattern formed by the
differences, we get this tree:

oeee  eooo  eeoe  ooeo  eeeo  oooe  eoee  oeoo  1 even or 1 odd
\  /        \  /        \  /        \  /
oeeo        eooe        eeoo        ooee     2 even, 2 odd
\_      _/              \_      _/
\    /                  \    /
oeoe                    eoeo           alternating
\_______    _______/
\  /
oooo                       all odd
|
+-> eeee --+                   all even
|          |
+----------+                   stays even!

This tells us two things: First, there are no numbers you can start
with and get differences with one of one parity and three of the
other; so if you are working backward trying to find a starting
pattern that will generate the differences you want, you will have to
stop when you come to this kind of pattern. (That's what made me
recognize the importance of parity in the first place.) Second, if
you want the longest possible sequence, you will probably be starting
with this kind of pattern, reaching all evens four steps later, and
then staying even forever. The only place you can lengthen the
sequence is within the all-even segment, since there is no limitation
there.

Now, how can we make a long sequence that is all even? Easy: take an
existing sequence and double each of the numbers. Then you can try to
put four more layers on top of it to make a longer sequence that
includes odd numbers. And when you've done that, you can repeat the
process. So all we're missing is how to (and whether we always can)
work backward to add steps to the top.

That brings me back to some other issues I discovered about working
backward. One was that if the numbers you have are like "oeee," it's
impossible, as I said. But there are other restrictions as well.

Let's take an example. Suppose we have four numbers a>b>c>d. Then our
differences will be

a-b, b-c, c-d, a-d

If we add the first three of these, we get the last:

(a-b)+(b-c)+(c-d) = a-b+b-c+c-d = a-d

To put this another way, if the differences are w, x, y, z, then

w+x+y-z = 0

Something like this will ALWAYS be true, regardless of the order of
the numbers: some sum or difference of the differences will equal
zero. And that is not true of any set of four numbers you choose; so
given w, x, y, z, you can't always find a, b, c, d such that their
differences will be w, x, y, z.

Here's one way to show that what I just said is true. Put the four
numbers in a square (which is one common way to present this problem):

a-------b
|       |
|       |
|       |
d-------c

Now go around the square clockwise, and on each side write the sign
of the first number minus the second (a-b, b-c, c-d, d-a):

+
a-------b
|       |
-|       |+
|       |
d-------c
+

Then the difference between each pair of numbers will be that sign
times the first number minus the second; and the first number minus
the second will be the sign times the difference. But since

(a-b)+(b-c)+(c-d)+(d-a) = 0

this tells us that the sum of the signs times the differences will be
zero:

+/-|a-b| +/- |b-c| +/- |c-d| +/- |d-a| = 0

+/-w +/- x +/- y +/- z = 0

Keep this picture of a square with signs on the edges in mind for the
future.

Now we know that a given set of numbers can't always be the result
of a difference step, because, for example, there is no way to add up
1, 2, 3, and 100 to give 0. But in many cases you can _modify_ a set
of numbers to make it possible.

Notice that if you add the same number k to each of a, b, c, and d,
then the differences will be unchanged. In our example, the
differences are 1, 1, 97, and 99; but if we add, say, 50 to each
number, the differences are still 52-51=1, 53-52=1, 150-53=97, and
150-51=99. So if we get 1, 2, 3, 100 by working backward from a
desired set of differences, 51, 52, 53, 150 will still give the same
differences.

How can we modify our numbers to make them a valid set of differences?
We can choose a set of four signs and try it out on them to see that
they don't work; we find that 1+2+3-100 = -94 rather than zero. But
if we add 94/2 = 47 to each number, we will be adding 47 three times
and subtracting it once, which adds 94 to the sum, making it zero. So
the numbers 48, 49, 50, 147 WILL work:

48+49+50-147 = 0

Notice that we have to choose three of one sign and one of the other
in order to do this; if all the signs are the same we can't get zero
from positive numbers, and if there are two pluses and two minuses,
adding k to each number will not change the sum.

This gives us some tools to work backward. Let's look at your
example, and try to improve it:

13, 104,  9,  0 oeoe
91,  95,  9, 13 oooo
4,  86,  4, 78 eeee
82,  82, 74, 74 eeee
0,   8,  0,  8 eeee
8,   8,  8,  8 eeee
0,   0,  0,  0 eeee

We should first be able to work backward two more steps, giving ooee
and oeee, or something like that. We first have to make an adjustment:

13 - 104 + 9 + 0 = -82

so we add 41 to each and have

54 - 145 + 50 + 41 = 0

Now we can find the step above this by adding and subtracting using
the signs we've got:

0            (as an arbitrary starting point)
0+54 = 54    (our second number)
54-145 = -91 (our third number)
-91+50 = -41 (our fourth number)
-41+41 = 0   (check: we do get back to the first number)

We don't want a negative number; but we can fix that just by starting
high enough. Let's add 91 to everything:

91, 145, 0, 50

Just to check, the differences from here are

54, 145, 50, 41
91, 95, 9, 13

and from here we continue with your numbers. So now we've added a new
step above yours, by replacing your first step with one that works.
And this step has the pattern "ooee," so we hope to be able to
continue one more step up. We'll find we have to add 2 to each number
in the newly added step, making it

93, 147, 2, 52 (ooee)

and the step above it will be

0, 93, -54, -52

which we can adjust to make it all positive:

54, 147, 0, 2 (oeoo)

(Of course, this "positivizing" step isn't really necessary, since
we'll be adjusting again to make a possible set of differences; but
it feels better to be always writing positive numbers.)

So our sequence at this point is

54, 147,  0,  2 eoee
93, 147,  2, 52 ooee
54, 145, 50, 41 eoeo
91,  95,  9, 13 oooo
4,  86,  4, 78 eeee
82,  82, 74, 74 eeee
0,   8,  0,  8 eeee
8,   8,  8,  8 eeee
0,   0,  0,  0 eeee

Now we'd like to go farther, but the single odd number tells us we
can't. To make it extendable, we can just double everything, so we
are back to "eeee" and have a chance of adding four more steps at the
top:

108, 294,   0,   4
186, 294,   4, 104
108, 290, 100,  82
182, 190,  18,  26
8, 176,   8, 156
164, 164, 148, 148
0,  16,   0,  16
16,  16,  16,  16
0,   0,   0,   0

I'll let you try extending this further. I haven't yet determined
whether we can expect this to work every time, and there are a few
kinds of roadblocks I haven't mentioned to you yet, so don't get
frustrated if you find you get stuck.

If you have any further questions, feel free to write back. I'd also
problem, other than just answers without explanations. (I did find on
the Web one sequence of 12 steps, but nothing to show that was
anything but a random guess.)

- Doctor Peterson, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
High School Number Theory
High School Puzzles

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search