Information for discovering an item-colour assignment in a combinatorial game

Question

We are given a set $S=\{i_1, i_2, \ldots, i_n\}$ of items and a set $C=\{c_1, c_2, \ldots, c_m\}$ of colours. Each item in $S$ is tinted with one colour $c\in C$. Let $\mathcal{A}$ be the set of all item-colour assignments where the total number of items in $S$ tinted with each colour $c\in C$ is equal to $\frac{n}{m}$ (assume that $n$ is a multiple of $m$).

We play a sequential game, where an item-colour assignment is (hiddenly) selected uniformly at random from $\mathcal{A}$ and at the beginning no information is known about the colour of any item. At each time step, we choose a pair $(i,c)$ where $i\in S$ and $c\in C$, and we receive the "binary information bit" representing whether $i$ is tinted with colour $c$ or not.

---

Question: How can we prove that, if we receive $\frac{nm}{8}$ such binary information bits, then there exists a constant $a>0$ such that in expectation it is not possible to find the colours of at least $(a\!\cdot\! n)$-many items in $S$?

Answer 1

Not a full answer, but some thoughts...

(First off, if $m$ is way too small or way too big, something weird might happen. So let's think of $m$ and $n/m$ both sufficiently large. For instance, if $m=1$, the problem is silly.)

Well... Clearly we can discover colors for at least $n/8$ of the items (in fact, we could promise at least this well even in the worst case by just asking about every color on each of the first $n/8$ items). We could probably do better, and the best constant might be $n/4$ or so.

Here are two heurisitcs (neither exact). Since neither of the below are the honest-to-God truth, I'm not bothering super much being exact in what follows. I wouldn't be surprised if there's a very nice way to view the problem so as to make it very clear, but I coudln't see it right away.

---

Quick and dirty approach: Suppose the coloring is actually selected where each item is given a uniformly random color and (simplifying assumption) suppose these assignments are independent. Then the best algorithm would be to just sequentially go down the line and ask about each item one at a time until you know what it is (then move to the next one). [Proving that this is literally the best algorithm is (1) probably not hard, and (2) also probably true...]

Suppose we use this algorithm. Let $X_i$ be the color used for item $i$, and let $Y_i = \begin{cases} X_i, \qquad &\text{if } X_i < m\\ m-1, \qquad &\text{if } X_i = m\end{cases}$ (so $Y_i$ is the number of questions we would need to determine the color of item $i$). Then each $X_i$ is independently uniformly distributed over $\{1,2, \ldots ,m\}$, and we want to know the greatest value of $T$ such that $Y_1 + Y_2 + \ldots + Y_T \leq nm/8$. The expected value of $T$ is therefore equal to $$ \mathbb{E}[T] = \sum_{j=1} ^{\infty} \mathbb{P}\left( Y_1 + Y_2 + \cdots + Y_j \leq \frac{nm}{8}\right) $$

To simply some more, this is approximately asking how many continuous uniform on $[0,1]$ i.i.d. random variables are needed to sum to a total of $n/8$ (only approximately since $X_i \neq Y_i$ and since $X_i$ is not continuous, but this will be pretty close if $m$ isn't too small). This has probably been worked out (and it's given by the infinite summation and integral over the cube given above), and I bet it involves a Taylor series for $e$. But if $n/8$ is big enough, then $T$ is (on average) something like $n/4$. In fact, this would be related to the law of large numbers (and/or the central limit theorem to get more exact stuff).

---

Entropy approach: (This would probably work if you push on it hard enough.) Here, I'll use binary entropy, and $\lg(x)$ will denote the log base $2$. First off, the number of ``item-color assignments" is exactly equal to

$$N = {n \choose \frac{n}{m}, \frac{n}{m}, \ldots , \frac{n}{m}} = \dfrac{n!}{(\frac{n}{m}!)^{m}}.$$

At a first pass, an estimate for $\lg(N)$ is (say) $\lg(N) \approx n \lg(m)$ [thinking $N \approx m^n$], but (i) we'll only need a lower bound on $\lg(N)$, and (ii) you can get as exact as you want. Now the initial entropy of the selection is exactly equal to $\lg(N)$ (since it was made uniformly at random), which is about $n \lg(m)$.

Now the issue is in figuring out how much entropy each question has on average. You just need an upper bound on this, and it could perhaps be true that a greedy strategy (like above) would be the best algorithm to minimize the entropy of what's left.

In any case, the entropy of the first question is exactly $\log(m) - (1- \frac{1}{m-1}) \lg(m-1) \approx \lg(m)/m$. The questions you ask in the middle of the process will be hard to analyze of course, but let's say (as seems reasonable) that the average entropy per question should still be in the ballpark of $c \lg(m) / m$ for some constant $c$ that's not too big.

If we had such a bound on the average entropy of each question, we could say that after $nm/8$ questions, the average entropy went down by at most $(nm/8) c \lg(m) /m = n\lg(m) c/8$. So after the questions, the entropy of the coloring is still (on average) at least $n \lg(m) (1 - c/8)$. And if $1 - c/8 = a > 0$, then this means there are still at least $na$ items whose colors are unknown (since the entropy of a distribution is at most the log of its support, and if there are only $M$ unknown positions at the end, this would have entropy at most $\lg(m^M) = M \lg(m)$).

---

I have an idea to make the entropy argument more rigorous, but I'll hold off in case a much simpler argument comes along. [My idea is to perhaps divide questions into two types. Type 1 questions have low entropy (e.g., they ask about an item for which the distribution over its colors is pretty close to uniform [e.g., at most $m/10$ colors have been ruled out]). Type 2 questions are those with high entropy. And hopefully it's not possible to ask too many questions of high entropy (or at least, there must have been a bunch of questions of low entropy for every question of high entropy).]