Guessing a triple of digits by knowing if you got at least one of them right 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.
 A: $13$ guesses are enough
Here is a continuation of your strategy.
"If we get $2$ trues, wlog they're $111$ and $222$."

*

*Guess $177$. If we get true, then $a=1$; otherwise, $a=2$.

*Guess $717$. If we get true, then $b=1$; otherwise, $b=2$.

*Guess $771$. If we get true, then $c=1$; otherwise, $c=2$.

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

*

*Guess $177$. If we get true, then $a=1$. Go to step 3.

*Guess $277$. If we get true, then $a=2$; otherwise, $a=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$.
