Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|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
2  
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

 
discard

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

Browse other questions tagged or ask your own question.