Subtraction PuzzleDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/