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.