Discrete Mathematics You have n coins exactly one of which i

Discrete Mathematics

You have n coins, exactly one of which is counterfeit. You know counterfeit coins weigh more than authentic coins. Devise an algorithm for finding the counterfeit coin using a balance scale1 . Express your algorithm in pseudocode. For n = 12, how many weighings does your algorithm use? SHOW YOUR WORK

Solution

We can make two piles

Each having n/3 coins, and keep them on the balance

If the left hand side of the balance is heavy or lesser in weight, then it implies the coin is present in the left pile, so we discard the right pile and pile kept asside and continue

If the balance is equal, then we discard both the coins present in the left pile and the right pile and take the pile which was not kept on balance with n/3 coins

After this step, we have discarded the 2n/3 coins and left with n/3 coins present, again divide the n/3 coins into three piles

Repeat this procedure until one coin is left

For 12 coins:

We will make 3 piles of 4 coins each:

Put first two piles each having 4 coins on the left hand side and 4 coins on the right hand side

Case 1: Balance is equal

It implies that the counterfeit coin is present in the remaining stack of 4 coins, hence we discard the left and right coins

And divide the 4 coins left asside into 2-2 coins,balance them which ever is heavier or lighter will contain the coin, now balance the remaining two coins to get the counterfeit coint

Case 2: Balance is not equal

It implies that the counterfeit coin is present in the left or right side of 4 coins, hence we discard the kept asside and other side coins

And divide the 4 coins into 2-2 coins,balance them which ever is heavier or lighter will contain the coin, now balance the remaining two coins to get the counterfeit coint

Hence the total weighings required are 3