2
$\begingroup$

I have 12 rocks, all have the same weight except for one rock, but I don‘t know which rock is. How do I know which rock is different from other, and also know that rock heavier or lighter, with maximum 3 comparating steps. My only tool is just a balance that can only compare the weight between the rocks.

$\endgroup$
  • $\begingroup$ This task won't be doable in the worst case. However, it can be done only in some best cases. $\endgroup$ – Shaurya Gupta Feb 7 '14 at 17:43
  • $\begingroup$ @MarkBennet I tried divide them first into 6 rocks for each arm of the balance, but it takes more steps :) than max steps needed $\endgroup$ – oentoro Feb 10 '14 at 4:43
  • $\begingroup$ There are three possible outcomes for each weighing - left-hand balance goes down, level or up. So split into $3$. It is possible to do $13$ rocks. $\endgroup$ – Mark Bennet Feb 10 '14 at 7:58
  • $\begingroup$ @MarkBennet 13 is not possible: There are 26 results to distinguish. If the first weighing invlves $k$ rocks on each side, there are $2k$ possibilities for result "$>$", also $2k$ for "$<$", and $26-4k$ possibilities for "$=$". Each of these counts must be $\le 9$. But $2k\le 9$ implies $k\le 4$ and $26-4k\le 9$ implies $k\ge 5$ - contradiction. $\endgroup$ – Hagen von Eitzen Feb 21 '14 at 11:01
  • $\begingroup$ @HagenvonEitzen - sorry, yes you are right - but you can do $13$ if you don't need to know heavier or lighter (though you get this information twelve times out of thirteen - there is a single rock you don't weigh at all, and if that is the odd one out you can't know which) $\endgroup$ – Mark Bennet Feb 21 '14 at 11:07
2
$\begingroup$

Since there are $3\times 3\times 3$ possible measurement results (3 rounds with 3 possible outcomes per round) and a total of $24$ possible results we have to distinguish (which rock and heavier or lighter), the task is barely doable. For example one has to make sure that the first weighing round produces "less", "equal", and "more" each in at most $9$ of the $24$ cases (and hence at least in $24-9-9=6$ cases). If we weigh three against three rocks, this is not the case as "equal" occurs in $12$ cases. And with five against five (or more) we find that "less" occurs in $10$ cases. So we must weigh four against four in the first round! If the rocks are $A, \ldots, L$ and the first round compares $ABCD:EFGH$ we learn:

  • If "less" then one of $A,B,C,D$ is light or one of $E,F,G,H$ is heavy. Now compare $ABE : CDF$. Now "less" leaves us with options $A$ or $B$ light or $F$ heavy; "equal" means $G$ or $H$ heavy; "more" means $E$ heave or $C$ or $D$ light.

  • If "equal" then one of $I,J,K,L$ is light or heavy. Next compare $IJ:AK$ (note that $A$ has correct weight!) Now "less" means $I$ or $J$ light or $K$ heavy; "equal" means $L$ light or heavy; "more" means $I$ or $J$ heavy or $K$ light.

  • If "more" is symmetric to "less"

At any rate, you are left with at most three possibilities after two weighings. It is easy to differentiate between at most three outcomes with one weighing:

If one rock can be light or heavy, compare it against a known good. Otherwise we have different rocks that may only be wrong in one direction. Take two of them an put them on different scales if they can be wrong of the same kind; or put them on the same scale and put two known-good rocks on the other side if they can be wrong of different kind.


This was easy, for a generalization to several fake rocks cf. this.

$\endgroup$
1
$\begingroup$

This is the 12 coins problem under the isomorphism f(coin)=rock. See http://mathforum.org/library/drmath/view/55618.html. To add some new to the link and the anwer by Hagen, the idea is maximize the information obtained in each step. How? Trying that each three possible results in each weighting be (almost) equiprobable. See Huffman coding.

$\endgroup$
0
$\begingroup$

You have 24 possible outcomes (rock #1 light, rock #1 heavy, ..., rock #12 light, rock #12 heavy). With 3 weightings you get only $2^3 = 8$ possible outcomes, so the problem has no solution.

$\endgroup$
  • 1
    $\begingroup$ Three possible outcomes in each weighting. $3^3=27>24$. $\endgroup$ – Martín-Blas Pérez Pinilla Feb 7 '14 at 18:11

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.