This is a generalisation of a question that recently came up while solving a TopCoder problem.
Suppose we have N blue counters, N red counters, N white counters, and so forth, K colours in total. We distribute them into B >= K buckets, such that there are not more than N counters in each. Show that we can always pick K different-coloured counters from a set of K different buckets (one from each).
(In the TopCoder problem K was fixed at 3, but here it's arbitrary.)
Intuitively this seems simple. I'm looking for a satisfactory simple argument, but I just can't see it. I only have the argument below, which seems more complex than necessary.
Using an induction argument, assume we can already pick Q < K different-coloured counters from Q different buckets. Now we'll attempt to show that Q+1 is possible.
If there is a colour we haven't yet picked in a bucket we haven't yet picked, pick it and we're finished. Otherwise, counters of this next colour (let's say "red" for simplicity) are in a subset of buckets that we have already picked. Divide the set of buckets into 3 sets: (1) currently picked & with red counters, (2) currently picked & no red counters, (3) non-picked & no red counters.
Consider the first of these sets. There are Z buckets with at least Z+1 colours (because there is red too). As there are at most NZ counters in total in these, while there are N*(Z+1) counters of these colours altogether, there must be at least N counters of these colours in some of the other two sets. If this is in the last set, then it's easy to see what to do to get Q+1. The remaining case is if it's in the middle set. The rest of the argument refers to the following diagram:
The diagram shows that when it's in the middle set, we use the same argument again to show that there have to be some of the left-of-the-line picked counters beyond the boundary. Continuing in the same way, the boundary will be pushed until, eventually, there will be some of our counters in the third set. Every time it's pushed, an arrow is drawn from a picked counter on the left of the line to similarly-coloured counters to the right of the line. When we eventually reach the unpicked set, the third diagram shows that there will be a bunch of arrows all going diagonally left to right. All arrows have unique colour. And the thick red arrow shows how to follow the arrows to update the choice of which colour counter is picked from each bucket to get Q+1.
I'm asking if anyone can think of a much simpler proof of the same statement.