You have n coins — they all look identical, and all have the same weight except one, which is heavier than all the rest. You also have a balance scale, on which you can place one set of coins on one side, and another set of coins on the other, and the scale will tell you whether the two sets have the same weight, and if not, which is the heavier set. (a) Assuming that n = 3^k , devise a strategy that will identify the heavy coin using at most k weighings in the worst case. (b) Without any assumption on n, devise a strategy that will identify the heavy coin using log3 n+O(1) weighings.

My thought so far is to divide the number of coins into a set of 3 piles and weigh 2 piles at a time. Then take the heavier pile and weigh it with the other pile. This is probably incorrect, but its all I've got.

  • 1
    $\begingroup$ Try to write out all information you can obtain for each case of outcome you get. Suppose your 3 piles are $A,B,C$ and you weight $A,B$. You have three distinct outcomes the balance can tell you, right? Writes what you know for each case. Then write what you need to do next for each case. $\endgroup$ – Apiwat Chantawibul Oct 8 '14 at 21:25

Split the pile into 3 groups. Then weigh any 2 against each other. If one is heavier, then keep it and discard the other 2 immediately. If they weight the same, then discard them both and keep the other one. Continue this until there is one left.

You will eliminate $2(n/3)$ with every iteration i.e. if we started with $n=3^k$ and we divide the size of the pile by three with every weighing then after the first weighing, $i=1$ we have $3^{k-1}$ coins remaining. When $k-i=0$ then there is one coin left. Cleanly the number of weighings is $log3(n).$


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.