New answers tagged


Let me consider the case $n = m$ for concreteness. Since the entropy of $A$ is $n\log n$ and each question results in at most one bit of information, at least $n\log n$ queries are needed. Suppose that a question is selected uniformly at random. The probability that the answer is zero is $(1-1/n)^n \approx 1/e$, and in that case, we can mark all the queried ...

Top 50 recent answers are included