# Thread: Numbers on the blackboard

1. ## 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.

2. Originally Posted by scipa
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.