1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Set of 3 numbers

  1. Sep 15, 2007 #1
    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 [tex]\leq[/tex] 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. jcsd
  3. Sep 15, 2007 #2
    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.
  4. Sep 15, 2007 #3
    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).
  5. Sep 15, 2007 #4


    User Avatar
    Science Advisor
    Homework Helper

    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.
  6. Sep 15, 2007 #5
    You need to state your problem much better.
  7. Sep 16, 2007 #6


    User Avatar
    Science Advisor
    Homework Helper

    Sorry, my solution isn't right. I'll think about it some more.
  8. Sep 16, 2007 #7
    There is nothing else to state.
  9. Sep 16, 2007 #8


    User Avatar
    Staff Emeritus
    Science Advisor

    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 [itex]x\le y[/itex]). 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).
  10. Sep 16, 2007 #9
    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.
  11. Sep 17, 2007 #10
    Anyone? This problem is harder than I thought, and I have until Friday to solve it.
  12. Sep 18, 2007 #11

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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).
  13. Sep 18, 2007 #12
    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
  14. Sep 19, 2007 #13

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: Set of 3 numbers
  1. Spanning set R^3 (Replies: 1)

  2. 3 number of a function (Replies: 2)