4
$\begingroup$

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:

Illustration of the proof

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.

$\endgroup$
  • 1
    $\begingroup$ You might consider the bipartite graph whose vertex are the colors of counters and the buckets. If a bucket contains $k$ pieces of counters of a certain color then there is exactly $k$ edge between the vertex corresponding to that color and the bucket. You have to find a covering of the colors. So you have to apply Kőnig's or Hall's theorem. $\endgroup$ – Leonhardt von M May 9 '15 at 11:44
  • $\begingroup$ Hall's theorem! Not again.... :) $\endgroup$ – Evgeni Sergeev May 9 '15 at 12:12
  • $\begingroup$ What does "not again" mean here? I don't speak English very well and I just cannot interpret your reaction. $\endgroup$ – Leonhardt von M May 9 '15 at 12:32
  • $\begingroup$ @LeonhardtvonM :) In other words, I've tripped over Hall's theorem in the past. In fact, in the last few months there was a TopCoder problem that was a thinly veiled Hall's theorem, so it's fresh in my mind, but I still failed to recognise it in just a slightly different disguise. $\endgroup$ – Evgeni Sergeev May 9 '15 at 14:00
1
$\begingroup$

Community wiki answer based on the comments so that the question an be marked as answered:

For each colour, consider the set of buckets in which it is represented. We want to pick $K$ different representative buckets for the $K$ different colours. The assumptions of Hall's theorem are fulfilled: Since every bucket contains at most $N$ counters, any $j$ colours are represented in at least $j$ buckets.

Thus we can apply Hall's theorem to conclude that the desired set of representatives exists.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.