The problem describes a process (which I'll call anamalgamation 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 theoutcomeof the amalgamation process. We want to show that if there are initiallyn1s then the outcome must be at least 1/n.

At each stage of the process, two numbers are chosen from the set. Call themaandb. They are replaced by the single number (a+b)/4. If we look at the numberaand 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 thatais in fact the outcome of an amalgamation process starting with a subset of the originaln1s. If this subset containsp1s thenais the outcome of an amalgamation process starting withp1s. Similarlybis the outcome of an amalgamation process starting withq1s.

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

Take an amalgamation process starting withn1s, and consider the final stage of this process, in which the two remaining elementsaandbare combined to form the outcomec=(a+b)/4. Sinceais the outcome of an amalgamation process starting withp1s, it follows from the inductive hypothesis thata≥1/p. Similarly,b≥1/q. Also, since this is the final operation in the amalgamation process,p+q=n.

Thereforec≥ ((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 putn=1994.