Best strategy for a combinatorial game

Question

Consider the following scenario. We have 20 balls and 100 boxes. We put all 20 balls into the boxes, and each box can contain at most one ball.

Now suppose we are given 5 chances to pick 20 out of 100 boxes. Let's say that each time we choose 20 boxes, they form a group of boxes. So in the end, we get to pick 5 groups (each consists of 20 boxes).

Each group of course, can contain 0 to 20 balls. In the end, we get a score, which is the maximum number of balls in any of the groups we chose. Our goal is to maximize our score.

A bad strategy is to just randomly choose the groups, in which case we will likely get a score of 0. A smarter way is to utilize the pigeonhole principle and choose 5 disjoint groups, in which case the pigeonhole principle tells us that at least one of the groups contain 20/5 = 4 balls. Thus our minimum score becomes 4.

In the general case, where we have $N$ boxes and $k$ balls, and are given $N/k$ chances to pick groups of size $k$, the strategy I described above seems to be optimal, which guarantees a score of $k^2/N$. On the other hand, if we are given $O(2^N)$ chances to pick groups, we can guarantee a max score of $k$. My question is, what is the optimal strategy to maximize our score when we are only given a polynomial number of groups. Can we do better than a guaranteed score of $k^2/N$?

Edit: for simplicity, I am assuming that $N/k$ is a constant. So all the asymptotics are with respect to $N$.

Answer 1

Let me address the case $k=N/2$. Consider a hypergraph whose edges are your groups. Then, basically, you are interested in the discrepancy of your hypergraph. The first estimate at the linked Wikipedia page, $\textrm{disc}\leq \lambda=\sqrt{2N\ln 2m}$, where $m$ is the nunber of edges, shows that you cannot guess more than $N/4+O(\sqrt{N\ln N})$ by a polynomial number of choices.

Surely, a similar argument may be applied for any case when the ratio $k/N$ is fixed, and even wider.

Answer 2

The question is a little ambiguous as to what it is asking. But the idea is clear and it is a nice question. As I interpret it, I think the answer might be no and that designs and finite geometries might provide examples.

Since you want the guaranteed score ,not the expected one, I interpret your problem as this: We select some number $c$ of $k$ element subsets from an $N$ set, say $G_1,\cdots,G_c$. Call these guesses or groups. Then someone else, knowing our choices, gets to pick $t \geq 1$ $k$-element subsets $T_1,\cdots,T_t,$ the target(s). Our score is the maximum of $T_j \cap G_i$. With $c=\frac{N}k$ (if that is an integer) we can be sure of a score of $\lceil\frac{k}c\rceil.$ Then the question is to bound our best score if $c$ is a polynomial in the size of $M=\frac{N}k$.

A design theory question is "How large a collection of $k$-element blocks can be chosen from a set of size $N$ so that each pair has intersection no larger than $\mu?$" Given a highly optimal example we might consider taking some, most, or all but one, as guesses and then one (or all) of the rest as targets.

One ambiguity is how $k$ and $N$ grow relative to each other. In your example $k=20$ and $N=100.$ The question might be different for large $N$ and $k=\frac{N}5$ compared to $k=2\sqrt{N}.$ Another is if you are concerned with polynomial size with respect to $N$ or $M=\frac{N}k.$

Here is the base set for some examples I was thinking of:

There is a field $\mathbb{F}=\mathbb{F}_q$ with $q$ elements for $q$ a prime power. This is integers $\bmod q$ for $q$ a prime. The Affine geometry $AG(q,d)$ consists of the $N=q^d$ points $(x_1,\cdots,x_d)$ with $x_i \in \mathbb{F}$ with lines, planes and higher dimensional subspaces defined in the obvious way. In $AG(q,3)$ there are $q^3$ points, $q^4+q^3+q^2$ lines of size $q$ and $q^3+q^2+q$ planes with $q^2$ points.

An ovoid in $AG(q,3)$ is a subset of $q^2$ points, no three collinear. It turns out that these exist (for example the points $(s,t,s^2+st+at^2)$ where the polynomial $x^2+x+a$ does not factor in $\mathbb{F}$.) It turns out that exactly $q^2$ of the planes intersect the ovoid in a single point and the other $q^3+q$ intersect it in exactly $q^2$ points. (Note, ovoids are generally defined in a projective space, but I think I translated correctly)

• I don't know that the $c=q^3+q^2+q$ planes are the optimal choice for that $c$ and $N=q^3, k=q^2.$ But it feels like they should be. Here $M=\frac{N}k=q$ so $c=O(M^3)$ and $\frac{k^2}N=q.$ If the target is an ovoid we have no improvement over the case $c=q$ of an arbitrary partition into $q$ groups.

  • I think there are $O(q^6)$ ovoids so we could take that many targets.

  • I suspect that we could take the guesses to be all the ovoids and the target to be a plane to have $c=O(M^6).$ Actually we could also throw all other planes into the guess collection. This would be nicer in a projective setting. I justify this by analogy below.

• For $N=q^{d},k=q$ and $c=q^{d-1}\frac{q^d-1}{q-1}=O(M^2)$ , I don't know that the lines of $AG(q,d)$ are an optimal choice of guesses, but again it seems as if it should be. Then having the target be the set of points $(1,t,t^2,\cdots,t^{d-1})$ for $t \in \mathbb{F}$ does allow a score of $2$ while $\lceil \frac{k^2}N \rceil=\lceil \frac1{q^{2d-2}} \rceil=1.$

There might be other examples of this flavor.

An analogy for the first example with $\mathbb{R}^3$ is if the guesses are the planes and the target is a sphere. Then these are $2$ dimensional in a $3$ dimensional setting and the intersections are one dimensional (so $q^2,q^3$ and $q$ in some sense.) In that setting the collection of all ovoids $a(x-u)^2+b(y-v)^2+c(z-w)^2=1$ is $6$-dimensional. Then if the target is a plane the intersections will be one dimensional. I suspect this translates into an example over finite fields though I didn't check very carefully. If so, $N=q^3,k=q^2,c=O(M^6)$ and the score $q$ is no better than for $c=M.$

Answer 3

I gave a longer answer before you clarified the problem. Here is a briefer one. I will mainly talk about $N=100$ and $k=20.$

Note that choosing $\frac{N}k$ groups the strategy and optimum outcome are the same for any of the four goals maximize/minimize the largest/smallest intersection. Only a partition into disjoint groups can ensure that the score is as small (or as large) as $\frac{k^2}N.$

Sticking to maximum intersection size with $N=100$ and $k=20$, one can be sure of a score of $20$ only by choosing $\binom{100}{20}\approx 5.4\cdot 10^{20}=O(N^{10})$ groups. Obviously there are lower numbers of groups that will ensure a score of at least $s$ for other $4 \leq s \lt 20.$ I will suggest that they are not much smaller in terms of polynomial order.

Consider this variation: You pick $a$ groups $X_1,\cdots,X_a$ and the other player picks $b$ groups $Y_1,\cdots,Y_b.$ (All groups $20$ out of $100.$) Your goal is to maximize the guaranteed maximum among the $ab$ sizes $|X_i\cap Y_j|.$

If still $a=5,$ how do things improved for larger $b?$ The strategy is still the same for you. Here $b=\binom{100}{20}-4$ is enough to ensure a score of $20.$ On the other hand, it could happen that for $b=\binom{20}4^5\approx2.7\cdot 10^{18}=O(N^9)$ the groups $Y_1\cdots Y_b$ are exactly the ones using $4$ boxes from each of $X_1,X_2,X_3,X_4,X_5.$

Whatever this does show, it would scale up similarly for larger $N$ and $k=\frac{N}5.$

What if we were back to $b=1$ but now $a$ is $O(N^{9})?$ That would be in the spirit of your exact question. I suppose that here you could give up on three of the boxes and pick your groups from the other $97.$ Then you certainly can't be sure of a score over $17.$ There are $\binom{97}{17} \approx 3.7\cdot 10^{18}$ ways to pick $17$ boxes. So $a$ that large would guarantee that score of $17.$ Actually, a group of $20$ would cover $1140$ sets of size $17$ so a smaller $a$ might still guarantee a score of $17$ but nothing smaller that about $3\cdot 10^{15}$ possibly could (with that strategy of ignoring three.)