Set of 3 numbers

1. Sep 15, 2007

Dragonfall

1. The problem statement, all variables and given/known data

Choose a set of 3 natural numbers. From here you can take two of them, say x, y, where x $$\leq$$ y, and replace them with 2x and y-x, respectively. Show that if you repeat this process, you will eventually end up with a set containing 0.

3. The attempt at a solution

I have no idea how to do this.

2. Sep 15, 2007

Kummer

This is just not true.
Consider (1,2,3)
Choose the last two to get (1,1,4)
Choose the last two to get (1,2,3)
Keep repeating this ...
You never get a zero in the set.

3. Sep 15, 2007

Dragonfall

OK, when I said "repeat this process", I mean that in the next iteration, you can choose any of the 3 numbers. For example (1,2,3) becomes (1,4,1), then (2,4,0).

4. Sep 15, 2007

AKG

Suppose x <= y <= z
If 2y > z, then replace y and z with 2y and z-y. You'll notice that each iteration leaves the sum of the numbers fixed, but this move increases the value of the largest number (the largest number was z, but we replaced it with 2y which is bigger by assumption), making the sum of the smaller two numbers decrease.
If 2y <= z, but 2x < y, then since y-x < y (unless x is 0, in which case we're done), if we replace x and y by 2x and y-x, we've necessarily decreased the value of the middle number. If 2x > y, then y-x < x, so replacing x and y with 2x and y-x necessarily decreases the value of the smallest number. If 2x=y, replace x and z with 2x and z-x, leaving you with (2x,y,z-y) = (y,y,z-y). Then replace y and y with 2y and y-y=0 and we're done.

Anyways, if we look at the number min{sum of smallest 2, value of smallest, value of middle} we find that this is a decreasing sequence if we make the choices as per above, and by well-foundedness, we eventually get 0. This is right, I wrote it up sloppily so some statements aren't technically correct but I need to run now.

5. Sep 15, 2007

Kummer

You need to state your problem much better.

6. Sep 16, 2007

AKG

Sorry, my solution isn't right. I'll think about it some more.

7. Sep 16, 2007

Dragonfall

There is nothing else to state.

8. Sep 16, 2007

HallsofIvy

Staff Emeritus
He stated it very clearly. If you start with (1, 2, 3) and "choose the last two", you are taking x= 2 any y= 3 (since we must have $x\le y$). Then "replace them with 2x and y-x, respectively": that is you replace x= 2 with 2(2)= 4 and y= 3 with 3- 2= 1. You get (1, 4, 1). If again, you choose the last two you now have x= 1, y= 4. Replace x= 1 with 2(1)= 2 and y= 4 with 4- 2= 2. You now have (1, 2, 2). If you "repeat" in the since of again choosing the last two numbers you have x= 2, y= 2 and get (1, 4, 0).

9. Sep 16, 2007

Dragonfall

Ok, you all know exactly what I mean. At each step you make a choice of two numbers x <= y and replace them with 2x and y=x, respectively. Show that it is possible by doing this repeatedly to obtain a set with 0.

10. Sep 17, 2007

Dragonfall

Anyone? This problem is harder than I thought, and I have until Friday to solve it.

11. Sep 18, 2007

matt grime

No he didn't. He misused the word 'will', which indicates that something must happen. As has been shown, it is easy to find (infinitely many) counter examples - pick any set {x,y,z} where x+y+z is not divisible by 3 (it is moderately interesting to see why this works).

12. Sep 18, 2007

bomba923

Not necessarily; any 3-element multiset {x,y,z} containing two instances of the same natural number (e.g, where x=y) will form a set containing zero upon replacing y with y-x and x with 2x, whether or not the sum of the initial elements is divisible by 3 (e.g.,start with {1,1,4}, let x=y=1 and replace 'y' with 'y-x' and 'x' with '2x' to form {0,2,4}, which clearly contains a zero).

Or, if one must start with a true set (where each element is unique), consider {1,3,4}, where 1+3+4=8, not divisible by 3. Let x=1 and y=3, which will form the set {2,2,4}; then let x=y=2, and you will form {4,0,4}, which contains a zero.

Last edited: Sep 19, 2007
13. Sep 19, 2007

matt grime

Well, there is someone else who doesn't understand the definition of the word 'will'.

The only way in which you are forced to accept that you *will* hit zero is if at some point your has to be multiset is {x,x,x}, as otherwise if you have two distinct elements, then choosing them will not give 0.

But as we know, the OP didn't mean 'will' in this , but that some choice of sequence of operations will give a 0.

Last edited: Sep 19, 2007