0
$\begingroup$

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?

Improve this question
$\endgroup$
7
  • $\begingroup$ It should be clearly stated the the choice of bins for each person is public knowledge, otherwise the answer is clearly no. $\endgroup$
    – Tony Huynh
    May 16, 2013 at 8:09
  • 2
    $\begingroup$ 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? $\endgroup$
    – Douglas Zare
    May 16, 2013 at 8:24
  • $\begingroup$ 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$. $\endgroup$
    – Brendan McKay
    May 16, 2013 at 11:46
  • $\begingroup$ @Tony Huynh That's true, the choice of bins for each person is public knowledge. Thanks for your reminding $\endgroup$
    – Charles
    May 17, 2013 at 13:45
  • $\begingroup$ @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? $\endgroup$
    – Charles
    May 17, 2013 at 13:54

0

Reset to default

Your Answer

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