2
$\begingroup$

I have $8008$ binary grids of size $6 \times 10$ (they are all grids with the property described below), which I want to distinguish between with at most $13$ queries. A query will determine if the cell $A_{i,j}$ of a grid is $0$ or $1$.

The grids all have a nice structure. If you find a $0$ in a cell, all cells above and to the right are guaranteed to be $0$. If you find a $1$, all cells below and to the left are guaranteed to contain $1$.

An example grid is

$$\begin{matrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 \\ \end{matrix}$$

For an unknown grid $A$ if a query $A_{4, 3}$ returned $0$ I could fill in all values above and to the right of it.

$$\begin{matrix} - & - & - & - & 0 & 0 & 0 & 0 & 0 & 0 \\ - & - & - & - & 0 & 0 & 0 & 0 & 0 & 0 \\ - & - & - & - & 0 & 0 & 0 & 0 & 0 & 0 \\ - & - & - & - & 0 & 0 & 0 & 0 & 0 & 0 \\ - & - & - & - & - & - & - & - & - & - \\ - & - & - & - & - & - & - & - & - & - \\ \end{matrix}$$


Since there are $8008$ grids, I believe it should be possible to distinguish the grids with at most $\log_2{8008} \approx 12.97 \lt 13$ queries. The best I've managed to do it is with 15 queries, by building a decision tree greedily (picking the query which divides the space as evenly as possible). I haven't found any algorithms that will build a minimal height decision tree in a reasonable length of time.

Is there any way to do this?

$\endgroup$
  • $\begingroup$ If this problem comes from an online programming contest or course, could you please add a URL in the question? If it comes from a book or a paper, a reference. If it comes from you own life and research, some background? All that information motivates and helps people answer your question faster and better. $\endgroup$ – Apass.Jack Oct 24 '18 at 5:24
  • $\begingroup$ If you have some existing code, can you share it through one of many online IDE such as repl.it? That could help people drastically, even if your code is very very rough. $\endgroup$ – Apass.Jack Oct 24 '18 at 5:27
  • $\begingroup$ There's no reason to expect 13 queries to be possible. All you can say is that at least 13 queries are needed in the worst case. $\endgroup$ – Yuval Filmus Oct 24 '18 at 7:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.