Guessing a triple of digits by knowing if you got at least one of them right

Question

Here is a rephrased version of problem $4$ in BMO $2016$ round $2$. I rephrased to make it clearer and shorter.

Given is a triple of digits $(a,b,c)$, where $a$, $b$, $c\in\{0,1,\dots,9\}$. Each turn we guess a triple of digits $(m,n,p)$, and instantly know whether the statement \[a=m~~\textsf{or}~~b=n~~\textsf{or}~~c=p\] is true (however, we are not informed which of the three equalities is (are) true). How many turns will we need at least so that we are guaranteed to determine $(a,b,c)$?

My idea is to first guess $000$, $111$,$\dots$, $999$. If we get a single true, then that is $(a,b,c)$.

If we get $2$ trues, Wlog they're $111$ and $222$. Then all possibilities are $$(a,b,c)=\begin{array}{ll} (1,1,2)&(2,1,1)\\ (1,2,1)&(2,1,2)\\ (1,2,2)&(2,1,1). \end{array}$$ If we get $3$ trues, Wlog they're $111$, $222$ and $333$. Then all possibilities are $$(a,b,c)= \begin{array}{lll} (1,2,3)&(2,3,1)&(3,1,2)\\ (1,3,2)&(3,2,1)&(2,1,3). \end{array} $$ I don't know what's the best strategy from here.

Answer 1

$13$ guesses are enough

Here is a continuation of your strategy.

"If we get $2$ trues, wlog they're $111$ and $222$."

1. Guess $177$. If we get true, then $a=1$; otherwise, $a=2$.
2. Guess $717$. If we get true, then $b=1$; otherwise, $b=2$.
3. Guess $771$. If we get true, then $c=1$; otherwise, $c=2$.

"If we get $3$ trues, wlog they're $111$, $222$ and $333$."

1. Guess $177$. If we get true, then $a=1$. Go to step 3.
2. Guess $277$. If we get true, then $a=2$; otherwise, $a=3$.
3. We know the value of $a$. Wlog, let $a=1$. Guess $727$. If we get true, then $b=2$ and $c=3$; otherwise, $b=3$ and $c=2$.

$10$ guesses are used in the question. At most $3$ further guesses are used above. We have used at most $13$ guesses.

$13$ guesses are needed in the worst case

Suppose we have a strategy of at most $12$ guesses. Let us apply that strategy.

Consider when we get all falses for the first $6$ guesses. There are at most $6$ different $m$'s that appear in the first $6$ guesses. So, there are at least $10-6=4$ different possible values left for $a$. Similarly, there are at least $4$ different possible values left for $b$ and for $c$ respectively. Wlog, suppose $xyz$ where $0\le a,b,c\le3$ is possible still.

Consider the next guess $m_7n_7p_7$. There are 4 cases.

• None of the $m_7,n_7,p_7$ is among $0,1,2,3$. We must get false since we know $a,b,c$ are among $0,1,2,3$. We have still at least $4^3=64$ possibilities for $abc$.
• One of $m_7,n_7,p_7$ is among $0,1,2,3$. Wlog, suppose $m_7=0$. It can happen that we get false. We are then left with at least $3\times4\times4=48$ possibilities.
• Two of $m_7,n_7,p_7$ are among $0,1,2,3$. Wlog, suppose $m_7=0$ and $n_7=0$. It can happen that we get false. We are then left with at least $3\times3\times4=36$ possibilities.
• All of $m_7,n_7,p_7$ are among $0,1,2,3$. Wlog, suppose $m_7=0$ and $n_7=0$ and $p_7=0$. It can happen that we get True. We are then left with at least $64-3\times3\times3=37$ possibilities.

In summary, whatever the $7$-th guess is, we could be left with at least $36$ possibilities for $abc$. Since in worst cases after each guess we could be left with at least one half of the current possibilities, after using all remaining $12-7=5$ guesses, we will be left with at least $\lceil\frac{36}{2^5}\rceil=2$ possibilities for $abc$ in the worst cases. That is, that strategy of at most $12$-guesses does not guarantee to determine $abc$.