An interesting version of the problem "balls into bins"

294 Views Asked by At

Consider n people, each has k identical balls. Each people choose k different bins from m bins, constrained by the condition that there are no two people choose exactly the same k bins. For instance, there are 6 people A,B,C,D,E,F, each hold 2 balls and there are 4 different bins①,②,③,④. If A choose ①②, B choose ①③, C choose ①④, D choose ②③,E choose ②④,and F choose③④, then we call it a proper configuration since no two people choose exactly the same 2 bins

Now each people flip a unbiased coin, if HEAD appears then he put all his ball into the k bins he has choosen, each bin with one ball. He will do nothing if TAIL appears. Here comes the problem, given a proper configration, everyone flip a coin and behave the way we described above. Can we infer the coin result of each people based on the number of balls in each bin?

1

There are 1 best solutions below

5
On BEST ANSWER

Not in general. For example, suppose there are four people $A,B,C,D$ and four bins 1,2,3,4, and suppose that $A$ chooses 1 and 2, $B$ chooses 3 and 4, $C$ chooses 1 and 4, and $D$ chooses 2 and 3. In this case, there's no way to distinguish between $A$ and $B$ flipping heads and $C$ and $D$ flipping tails, versus $A$ and $B$ flipping tails and $C$ and $D$ flipping heads.

If you want the choices of bins to be sufficient to determine the choice of people, then you need the bin choices to be linearly independent as vectors in $\mathbb{Z}_2^m$. That is, the choices should be the basis codewords for a binary linear code of type $[m,k,2]$.

Edit: As Hagen von Eitzen points out, using a binary linear code is sufficient to determine the coin flips, but it isn't necessary.