We are given $2001$ balloons and a positive integer $k$. Each balloon has been blown up to a certain size (not necessarily the same for each balloon). In each step it is allowed to choose at most $k$ balloons and equalize their sizes to their arithmetic mean. Determine the smallest value of $k$ such that, whatever the initial sizes are, it is possible to make all the balloons have equal size after a finite number of steps.
Problem
Source: Italy TST 2001
Tags: induction, calculus, integration, combinatorics unsolved, combinatorics
30.09.2008 21:14
The answer is 29. In general, if there are $ n$ balloons, the answer is $ P(n) =$ largest prime divisor of $ n$. To show that $ k = P(n)$ is sufficient, use induction on $ n$. If $ p = P(n)$ is the largest prime dividing $ n$, let $ n = pm$. Divide the $ n$ balloons into $ p$ groups of $ m$ each, and using the induction hypothesis to equalize each set of $ m$ balloons by averaging at most $ P(m) \leq p$ at each step. Number the balloons at each such set $ 1$ through $ m$, and now equalize all the number 1's (there are $ p$ of them), then all the number 2's, etc. through all the ones numbered $ p$. The result has all $ n$ balloons equal. Showing that $ k = P(n)$ is necessary is a nice opportunity to introduce the useful concept of $ p$-integers. For a given prime number $ p$, a rational number $ a/b$ is a $ p$-integer is $ \gcd(a,b) = 1$ (namely, the fraction is written in lowest terms) and $ p$ does not divide $ b$. Thus $ 5/12$ is a 7-integer, and $ 3/6$ is a 3-integer since $ 3/6 = 1/2$. An ordinary integer is a $ p$-integer for any $ p$. The important thing about $ p$-integers is that they can be added, subtracted and multiplied. Indeed, $ \frac {a}{b} + \frac {c}{d} = \frac {ad + bc}{bd}$. This fraction may not be reduced, but regardless, if $ p$ divides neither $ b$ nor $ d$ then it doesn't divide any divisor of $ bd$ either. The same goes for the product $ \frac {ac}{bd}$. It follows that if $ x_1,\ldots,x_k$ are $ p$-integers and $ p$ doesn't divide $ k$, then the average $ \frac {1}{k}(x_1 + x_2 + \cdots + x_k)$ is a $ p$-integer. So, if the initial sizes of the balloons are all rational $ p$-integers, and if we repeatedly equalize groups of various sizes that are not divisible by $ p$, then the balloon sizes remain $ p$-integers. Now make the following assumptions: there are $ n$ balloons, $ p$ divides $ n$, $ p > k$, the initial sizes of the balloons are all integers, and the sum $ M$ of those sizes is not divisible by $ p$. This can obviously always be managed. Since $ p$ doesn't divide any number less than or equal to $ k$, the balloons will always have $ p$-integral size. But to make them equal we must make each balloon have size $ M/p$ which is not a $ p$-integer since $ M$ is not divisible by $ p$. This contradiction shows that $ k$ must be at least as large as any prime dividing $ n$ in order for us to be able to equalize any initial set of balloons.