IMO 1967 LL MON31

Origin: MON

Problem

An urn contains balls of k different colors; there are ni balls of the ith color. Balls are drawn at random from the urn, one by one, without replacement. Find the smallest number of draws necessary for getting m balls of the same color.

Solution

Suppose that n1 \leqn2 \leq\cdot \cdot \cdot \leqnk. If nk < m, there is no solution. Otherwise, the solution is 1 + (m −1)(k −s + 1) +  i<s ni, where s is the smallest i for which m \leqni holds.