### 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}

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}