In two bowls there are in total ${N}$ balls, numbered from ${1}$ to ${N}$. One ball is moved from one of the bowls into the other. The average of the numbers in the bowls is increased in both of the bowls by the same amount, ${x}$. Determine the largest possible value of ${x}$.
Problem
Source: Nordic Mathematical Contest 2002 #2
Tags: combinatorics, maximum
14.07.2019 18:52
Bumppppp
15.07.2019 15:47
Bumppppp
16.07.2019 18:12
Bumppppp
16.07.2019 18:17
WLOG let the first bowl have the smaller average. If \(N>2\), then \(x=\frac{1}{2}\) is obviously achievable - for instance, start with \([1],[2,3,\dots N]\) and move the \(2\) ball. It's trivial to check both averages increase by \(\frac{1}{2}\). Now assume \(x>\frac{1}{2}\) is possible for some \(N\), and let the first bowl initially have \(k\) balls in it, summing to \(S\). Obviously \(S\geq 1+2+\dots k=\frac{k(k+1)}{2}.\) Further let the ball moved be of value \(a\). The average of the first bowl increases by \(\frac{S+a}{k+1}-\frac{S}{k}>\frac{1}{2}.\) The average of the second bowl increases by \(\frac{\frac{N(N+1)}{2}-S-a}{N-k-1}-\frac{\frac{N(N+1)}{2}-S}{N-k}>\frac{1}{2}.\) Solving for \(S\) yields \(S<\frac{k(k+1)}{2}\), contradiction. Hence \(x=\frac{1}{2}\) for all \(N>2\).