8
$\begingroup$

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})$?

Improve this question
$\endgroup$
7
  • $\begingroup$ Note: it is important that Bob's score is a function of $m$ and $k$, and not of the world size $n$. If Bob's score were a function of $n$ and $k$, then both the upper and lower bounds would have been $n/k$: lower bound same as above, and upper bound when Alice selects $n/k$ disjoint sets. $\endgroup$
    – Erel Segal-Halevi
    Commented May 2, 2017 at 14:28
  • 3
    $\begingroup$ Clarification in case anybody read this the same way as me: we are counting green points with some property, not $k$-sets containing exactly one green point. $\endgroup$
    – Ben Barber
    Commented May 2, 2017 at 15:03
  • $\begingroup$ @BenBarber yes, if there are several different sets with the same single green item, only one is counted towards Bob's score. Added clarification. $\endgroup$
    – Erel Segal-Halevi
    Commented May 3, 2017 at 7:15
  • $\begingroup$ Doesn't the probability for an item $x$ to be a singleton depend on the number $m_x$ of sets (chosen by Alice) that contain it? In each of these, it has a probability of $p(1-p)^{k-1}$ of 'attaining singleton status through this set'. The chance of being singleton should be higher than that (depending on the structure of the sets chosen by Alice, though). $\endgroup$
    – monkeymaths
    Commented May 3, 2017 at 12:48
  • 1
    $\begingroup$ @WlodAA I had in mind the definition common in computer science (of Knuth), see en.wikipedia.org/wiki/Big_O_notation#Big_Omega_notation $\endgroup$
    – Erel Segal-Halevi
    Commented Oct 19, 2020 at 9:01

2 Answers 2

Reset to default
2
$\begingroup$

None of those seems correct if $k\ge \log m$. Consider your construction described for the upper bound, except that we make divide all elements into $s$ groups of size $\frac kt$, and Alice picks the $\binom st$ sets that contain exactly $t$ groups. Then, as you've mentioned, Bob's score is at most $s$, since he can win at most one singleton per group. In fact, Bob's score is $s-t+1$, which is independent of $k$. I'm not sure what choice of $s$ and $t$ optimizes this, but the best score should be around $\log m$, provided that $k\ge \log m$. Of course, this leaves the problem open and interesting for small $k$.

Improve this answer
$\endgroup$
5
  • $\begingroup$ If $k\geq \log_2{m}$, then $m^{1/k}\leq 2$, so my upper bound gives $O(k)$. So your construction improves this to $O(\min(k,\log{m}))$, right? $\endgroup$
    – Erel Segal-Halevi
    Commented May 3, 2017 at 12:49
  • $\begingroup$ @Erel I think so. $\endgroup$
    – domotorp
    Commented May 3, 2017 at 13:01
  • $\begingroup$ This construction doesn't actually improve on Erel's construction. Take $m= { s \choose t}$ for some $t \leq k$. Let $n$ be so that $n-k = s-t$, in particular, $n \geq s$. Then we have ${ s\choose t} = { s \choose s-t} = { s \choose n-k} \leq {n \choose n-k} = {n \choose k}$ so Erel's construction gets the same upper bound with a larger $m$. Instead, your improvement comes from a better estimate of the inverse binomial function in this range. $\endgroup$
    – Will Sawin
    Commented May 4, 2017 at 17:32
  • $\begingroup$ @Will I thought $m$ and $k$ were both parameters in which we try to optimize. $\endgroup$
    – domotorp
    Commented May 5, 2017 at 0:06
  • $\begingroup$ @WillSawin Where did your answer go? I thought it was (almost) correct. $\endgroup$
    – Erel Segal-Halevi
    Commented May 6, 2017 at 17:37
1
$\begingroup$

Alice can select $\ m:=2\cdot n\ $ sets, each having $\ k:=2^{n-1}\ $ elements, in such a way that poor Bob can score at the most $\ n\ $ green singletons and not more ($\ n=2\ 3 \cdots$).

Thus Bob's best score $\ B(m\ k)\ $ for even $\ m\ $ and $\ k=2^{m/2}\ $ is reduced by Alice to $\ m/2.$

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .