Alice and Bob play the following zero-sum game, parametrized by two integers $m$ and $k$:

- Alice picks $m$ sets, each of which has $k$ items.
- Bob colors some items in green.
- Bob's score is the number of
*distinct singletons*, where a singleton is defined as a green item contained in a set in which all other $k-1$ items are uncolored (if there are several different sets with the same single green item, only one is counted towards Bob's score).

**What is the highest score Bob can guarantee to himself, as a function of $m$ and $k$?**

A lower bound is $\Omega(m^{1/k})$.

*Proof.*Suppose Bob colors each item in the world (=the union of all Alice's sets) with probability $p$, independently of the others. The probability of each item to be a singleton is: $p\cdot(1-p)^{k-1}$; this is maximized when $p=1/k$, and the maximum is at least $1/(e\cdot k)$. Then, the expected number of singletons is at least $n/(e\cdot k)$, where $n$ is the world size. Therefore, Bob can always guarantee to himself a score in $\Omega(n/k)$. The number of sets $m$ is at most ${n \choose k}$ which is at most $(n\cdot e/k)^k$, so $n \in \Omega(k\cdot m^{1/k})$, so Bob's score is in $\Omega(m^{1/k})$.An upper bound is $O(k\cdot m^{1/k})$.

*Proof.*Alice can choose $n$ such that $m={n \choose k}$, and select all $k$-element subsets of the integers $1,\ldots,n$. Bob can get at most $n$ singletons. In fact he can get exactly $n-k+1$ singletons, by coloring all items except $1,...,k-1$. So Bob's score is in $O(n) = O(k\cdot m^{1/k})$.

So what is the correct expression? Can Alice always force Bob to get at most $O(m^{1/k})$? Or can Bob always get at least $\Omega(k\cdot m^{1/k})$?