Best strategy for a combinatorial game

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 k2/N. On the other hand, if we are given O(2N) 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 k2/N?

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

Answer

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, discλ=2Nln2m, where m is the nunber of edges, shows that you cannot guess more than N/4+O(NlnN) 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.

Attribution
Source : Link , Question Author : GavinZZZ , Answer Author : Ilya Bogdanov

Leave a Comment