Finding the unique rock with its weight
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.
Solution 1:
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.
Solution 2:
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.