Yet another coin problem. Read this today in "Heard from the Street". Found it interesting.
Problem: You are given a set of scales and 90 coins. The scales are of the old balance variety, that is a small dish hangs from each end of the rod that is balanced in the middle. You must pay 100$ every time you use the scales.
The 90 coins appear to be identical. In fact, 89 of them are identical and one is of a different weight. Your task is to identify the unusual coin and to discard it while minimizing the maximum possible cost of weighing. What is your algorithm to complete this task?
Note that the unusual coin may be heavier than the others or it may be lighter. You are asked to both identify it and determine whether it is heavy or light.
Previously asked coin puzzles:
Another Coin Problem
Five Thieves and Bounty
Update (18/02/10): Solution posted by me in comments!! A non-optimal but simpler solution posted by Bhanu (M.Tech Student, CSE, IITB). Another solution posted by Suman in comments!! Thanx