Skip to main content
2 of 5
added 14 characters in body
alex
  • 976
  • 4
  • 14
  • 26

a probability question related to extremal combinatorics

$k$ people play the following game: person $i$ independently picks a random subset $S_i$ of $\{ 1,2,\ldots,n \}$ according to some distribution which is the same for all persons. If some $S_i$ is contained in $\cup_{j \neq i} S_j$, they all lose; else, they all win. What distribution maximizes the probability of winning?

I am actually only interested in the case where $n/k$ is an integer, in which case I would conjecture that the optimal distribution is for each person to pick a random subset with $n/k$ elements. I can prove this only for $k=2$, in which case it follows straightforwardly from Sperner's theorem.

alex
  • 976
  • 4
  • 14
  • 26