Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
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 
patterns I had found) is

   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 
be interested in hearing if you have any more information about the 
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

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/