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$.
