### Another Coin Problem

Jaadu asked me this question in a Convex Optimization Class this semester. I was able to solve it. He said it was in one of Diwan Sir tutorials. :) Interesting puzzle!! You are given N coins (assume N to be of the form 2^k). Some are light and other are heavy.You are given one weighing machine. What is the number of weighing required to find the number of coins that are heavy? A hint: Try to divide the coins in two equal parts such that each have both have same number of heavy coins. Previously asked coin puzzles: Coins Puzzle Consecutive Heads Five Thieves and Bounty Update (11/12/09): Solution in comments!! Update (11/12/11): Weighing machine here is a weighing balance. Its a function isXgtY {Input X: Set of Weights, Input Y: Set of Weights, Output Bool 1 if X>Y and 0 if X<=Y}