2
$\begingroup$

I have $5$ red, $5$ green and $5$ black rocks. They each contain a "fake" one, so we have $3$ fake rocks, and they all have different color. I can chose arbitrary set of rocks and know if there is a fake rock or not. I need to find all $3$ fake rocks after $7$ questions.

There are $5*5*5$ cases, and cause $2^7$ is greater than $125$, we can assume that there is a solution.First set I chose so. $1$ red , $1$ green and $1$ black, if here is not fake then I can find them using $6$ more question (2 question for each 4 rock). But I can't go on when the answer is yes.

$\endgroup$
  • $\begingroup$ Can we choose all three rocks of the same color? $\endgroup$ – Banach Tarski Mar 28 '16 at 5:50
  • 1
    $\begingroup$ I suspect your first question has to be different. It doesn't divide the cases into half close enough. I.e. there is more than $2^6$ cases remaining in the yes case. $\endgroup$ – Ian Miller Mar 28 '16 at 5:54
  • 3
    $\begingroup$ @IanMiller: really? There are $4^3=64$ possibilities that yield "no" for that first question, leaving $125-64=61<2^6$ possibilities that yield "yes". $\endgroup$ – Greg Martin Mar 28 '16 at 6:58
  • 1
    $\begingroup$ Hmm must have miscounted. $\endgroup$ – Ian Miller Mar 28 '16 at 8:44
  • $\begingroup$ Related: math.stackexchange.com/q/1707332/162300 $\endgroup$ – filipos Mar 29 '16 at 17:31
0
$\begingroup$

I'll denote by $R_i$, $G_i$, $B_i$ the propositions that the $i$-th red, green or black rock, respectively, is fake, and I'll use addition and juxtaposition to denote logical OR and AND, respectively.

Any two cases can be distinguished by one question. Four cases are readily split $2/2$ if there is a colour that splits $2/2$, $2/1/1$ or $1/1/1/1$; that leaves only the case where all three colours split $3/1$, and in that case the subset consisting of two of the $1$s splits the cases $2/2$. Thus any four cases (or less) can be distinguished by two questions.

If the answer to your first question $R_1+G_1+B_1$ is "yes", your next question can be e.g. $R_1+G_2$.

If the answer to $R_1+G_2$ is "no", then you know $(R_1+G_1+B_1)\overline{R_1}\,\overline{G_2}=(G_1+B_1)\overline{R_1}\,\overline{G_2}$, so red factors out (two questions) and then you can ask $B_1$ to split the remaining $8$ cases $4/4$.

If the answer to $R_1+G_2$ is "yes", then you know $(R_1+G_1+B_1)(R_1+G_2)=R_1+B_1G_2$, which has $29$ cases. You can then ask $G_1+G_2$.

If the answer to $G_1+G_2$ is "no", then you know $(R_1+B_1G_2)\overline{G_1}\,\overline{G_2}=R_1\overline{G_1}\,\overline{G_2}$, so red is solved and black and green factor. Then you can ask $B_1+G_3$; if the answer is "no", black and green still factor, with $2\times4$ cases, and if the answer is "yes", asking $B_1$ splits the remaining cases $3/4$.

If the answer to $G_1+G_2$ is "yes", then you know $(R_1+B_1G_2)(G_1+G_2)=R_1(G_1+G_2)+B_1G_2$, which has $14$ cases. You can then ask $R_2+G_1$.

If the answer to $R_2+G_1$ is "no", then you know $(R_1(G_1+G_2)+B_1G_2)\overline{R_2}\,\overline{G_1}=G_2(R_1+B_1\overline{R_2})$, which has $8$ cases that split $4/4$ if you ask $B_1$.

If the answer to $R_2+G_1$ is "yes", you know $(R_1(G_1+G_2)+B_1G_2)(R_2+G_1)=R_1G_1+R_2B_1G_2$, and asking $B_1$ splits the remaining $6$ cases $2/4$.

Here's the code I used to find this solution.

| cite | improve this answer | |
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.