Choose 3 Natural Numbers to Show How 0 Can be Obtained

[Dragonfall]

Homework Statement

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.

The Attempt at a Solution

I have no idea how to do this.

 

[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.

 

[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).

 

[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.

 

[Kummer]

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).

You need to state your problem much better.

 

[AKG]

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

 

[Dragonfall]

You need to state your problem much better.

There is nothing else to state.

 

[HallsofIvy]

Homework Statement

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.

The Attempt at a Solution

I have no idea how to do this.

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.

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).

 

[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.

 

[Dragonfall]

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

 

[matt grime]

He stated it very clearly.

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).

 

[bomba923]

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).

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.

 

[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.