BT 6: Scales IVYou have a tip-scale. You have N coins. You know one of the coins is counterfeit, but you don't know whether it weighs more or less than a true coin. You must identify the counterfeit coin using the scale no more than M times.
Your challenge is to determine the following: how large can N be, given M? Also, how large must M be, given N?
Note: as you might have already suspected, the Scales III brain-teaser was set up specifically to help with this problem: an inductive-style argument will work well here.