1
$\begingroup$

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)?

$\endgroup$
5
  • $\begingroup$ Just a wild guess: Maybe the bloom filters can help you. (Caveat emptor: That's just a guess. I haven't slept on it!) $\endgroup$ Jan 10, 2011 at 8:11
  • $\begingroup$ I'm not sure what tags should be put on this problem, especially the "labeling" tag. Feel free to edit them. $\endgroup$ Jan 10, 2011 at 8:15
  • $\begingroup$ 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? $\endgroup$
    – domotorp
    Jan 10, 2011 at 8:24
  • 3
    $\begingroup$ 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. $\endgroup$
    – Kaveh
    Jan 10, 2011 at 10:32
  • $\begingroup$ I think it would be interesting to see the answer if one can look at the names of all the boxes. -- Rachit $\endgroup$
    – user3154
    Jan 10, 2011 at 19:46

1 Answer 1

1
$\begingroup$

The questions is what you are allowed to do, can you look at the names of all the boxes or you just one to decide for a given ball and box whether the ball is in that box? I suppose y is at most x in the problem.

If you can look at only one box, then its name has to describe which balls are in it, so you would need x/y log x bits/boxes.

If you can look at all the box names, then the problem becomes to count the number of ways you can evenly distribute x balls into y boxes, I think this will also give x/y log x bits/boxes though I am not 100% sure.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.