Results 1 to 2 of 2

Math Help - Numbers on the blackboard

  1. #1
    Newbie
    Joined
    Jul 2008
    Posts
    19

    Numbers on the blackboard

    To play the game FADEOUT, you begin by writing any set of 1994 numbers on the blackboard. You are then permitted to erase any pair of them, say a and b, and replace them by the number (a+b)/4. You continue this process 1993 times, after which only one number remains on the blackboard.

    Suppose that at the beginning of the game, all 1994 numbers on the board are 1. Prove that the number left at the end will never be less than 1/1994.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by scipa View Post
    To play the game FADEOUT, you begin by writing any set of 1994 numbers on the blackboard. You are then permitted to erase any pair of them, say a and b, and replace them by the number (a+b)/4. You continue this process 1993 times, after which only one number remains on the blackboard.

    Suppose that at the beginning of the game, all 1994 numbers on the board are 1. Prove that the number left at the end will never be less than 1/1994.
    The problem describes a process (which I'll call an amalgamation process) whereby one starts with a set of numbers which are all equal to 1, and combines them together pairwise in a sequence of operations, until there is only one number remaining. I'll call this number the outcome of the amalgamation process. We want to show that if there are initially n 1s then the outcome must be at least 1/n.

    At each stage of the process, two numbers are chosen from the set. Call them a and b. They are replaced by the single number (a+b)/4. If we look at the number a and trace back where it came from, we see that it is either one of the original 1s, or it the result of combining two other numbers. If we continue tracing these numbers back, we see that a is in fact the outcome of an amalgamation process starting with a subset of the original n 1s. If this subset contains p 1s then a is the outcome of an amalgamation process starting with p 1s. Similarly b is the outcome of an amalgamation process starting with q 1s.

    The idea is to prove by induction that the outcome of an amalgamation process starting with n 1s is at least 1/n. This is trivially true for n=1. Suppose as a (strong) inductive hypothesis that it is true for all numbers less than n.

    Take an amalgamation process starting with n 1s, and consider the final stage of this process, in which the two remaining elements a and b are combined to form the outcome c=(a+b)/4. Since a is the outcome of an amalgamation process starting with p 1s, it follows from the inductive hypothesis that a≥1/p. Similarly, b≥1/q. Also, since this is the final operation in the amalgamation process, p+q=n.

    Therefore c ≥ ((1/p) + (1/q))/4 = (p+q)/4pq. We want to show that this is ≥1/(p+q). Equivalently, we must show that (p+q)^2≥4pq. But this follows from the fact that (p+q)^2(p-q)^2 = 4pq. That completes the inductive proof. All that remains is to put n=1994.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: August 29th 2011, 03:18 AM
  2. Replies: 1
    Last Post: September 27th 2010, 04:14 PM
  3. Replies: 8
    Last Post: September 15th 2008, 05:33 PM
  4. Replies: 3
    Last Post: April 10th 2008, 06:58 PM
  5. Proving Lucas Numbers and Fibonacci Numbers
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 19th 2008, 12:33 AM

Search Tags


/mathhelpforum @mathhelpforum