Naming the Boxes

Here is a puzzle (which I am sure somebody must have studied in TCS):

Suppose I have $x$ balls, each having a unique $O(\log x)$ bit name (the names have no structure). These balls are distributed into $y$ boxes, each box containing equal number of balls.

I want to name each of the boxes such that, given the name of one of the balls, I can identify the box that contains the ball?

What is the minimum number of bits required to name the boxes? How does the solution change if some balls have similar names (i.e., if names are not unique)?

• Just a wild guess: Maybe the bloom filters can help you. (Caveat emptor: That's just a guess. I haven't slept on it!) Jan 10 '11 at 8:11
• I'm not sure what tags should be put on this problem, especially the "labeling" tag. Feel free to edit them. Jan 10 '11 at 8:15
• Can you look at the names of all the boxes or is the problem more like to decide if a given box contains a given ball? Jan 10 '11 at 8:24
• I am not sure if this is a research-level question and Math.SE (or MO) might be more suitable. Just to make sure I understand the question correctly, we have a function $f:[n] \rightarrow [m]$ s.t. $|f^{-1}(k)|=\frac{n}{m}$ for all $k \in [m]$, and we want to compute the amount of information (number of bits) needed to describe this function, I don't understand what is the relation with where this information is placed. An obvious upperbound is $n \lg m$. It will probably help if you explain the motivation behind the question and what you have got by yourself. Jan 10 '11 at 10:32
• I think it would be interesting to see the answer if one can look at the names of all the boxes. -- Rachit
– user3154
Jan 10 '11 at 19:46