Probably Too Easy

Alright, I was going to post this earlier because the solution to the counterfeit masses problem is really easy, but then my weekend got really occupied.

So, the solution is as follows:
Split the 27 coins into 3 piles of 9. Weigh two of the piles against eachother, whichever is heavier has the counterfeit coin and if neither is heavier the coin is in the third pile. Next, split the 9 into 3 groups of 3, and weigh two of those against eachother to find which pile of 3 has the counterfeit coin. Finally weigh two of the coins in the final pile of 3 against eachother to find the coin.

Its really a simple trinary search, this problem will only trip people up if they try to do a binary search not realizing that you always gain information about the coins you don't weigh.

Its also easy to see (and prove by induction) that with N measurements you can solve the problem with 3N coins. Also this solution is optimal, you cannot do more than 3N coins with only N measurements (also provable by induction).

I'll post the more difficult problem later today.

No comments: