MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 chosen, each bin with one ball. He will do nothing if TAIL appears. Here comes the problem, given a proper configuration, 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?

share|cite|improve this question
It should be clearly stated the the choice of bins for each person is public knowledge, otherwise the answer is clearly no. – Tony Huynh May 16 '13 at 8:09
If you find one ball in each of the $4$ bins, this could come from $A+F$, $B+E$, or $C+D$. Is that really what you wanted to ask? – Douglas Zare May 16 '13 at 8:24
This is a question about enumerating bipartite graphs with given degree sequences, under a weak condition that two vertices on one side can't have the same neighbours on the other side. Under reasonable conditions the number of solutions will grow faster than exponentially as $m,n\to\infty$. – Brendan McKay May 16 '13 at 11:46
@Tony Huynh That's true, the choice of bins for each person is public knowledge. Thanks for your reminding – Charles May 17 '13 at 13:45
@Douglas Zare I kown there eixsts multiple results sometimes i.e. we cannot infer the results of each people. Actually,what i want is some konwledge on the probability that this situation occurs.Put it another way, given m,n and k, can we bound the probability that we couldn't infer a unique result? – Charles May 17 '13 at 13:54

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.