Consider the following problem: Suppose we have nine identical-looking colas num
ID: 3576896 • Letter: C
Question
Consider the following problem: Suppose we have nine identical-looking colas numbered 1 trough 9 and only one of the coins is heavier than the others. Suppose further that you have one balance scale and are allowed only two weighings. Develop a method for finding the heavier counterfeit coin given these constraints. Suppose we now have an integer n (that represents n coins) and (only one of the coins is heavier than the others. Suppose further that n is a power of 3 and you are allowed log_3^n weighings to determine the heavier coin. Write an algorithm that solves this problem. Determine the time complexity of your algorithm.Explanation / Answer
a. Let's number the coins from 1 to 9 and divide the coins in 3 groups.
we have coins grouped as:
Group 1 -> (1,2,3) Group 2 -> (4,5,6) Group 3 -> (7,8,9)
now we first way Group1 and Group2
Now there are 3 possibilities:
1. Either Group1 is heavier than Group2
2. Group2 is heavier than Group1
3. Group1 and Group2 are equal
So, if both the groups are equal we have the heavier coin in Group3 or else we can take the heavier group from Group1 or Group2.
Now, suppose Group3 was heavier of Group1 and Group2, we name the Group3 coins (A,B,C)
Now we weigh coinA and coinB
Now there are 3 possibilities:
1. Either A is heavier than B
2. B is heavier than A
3. A and B are equal
So, if A is the heavier coin then A is answer or else B and if both coinA and coinB are equal then coinC is the answer.
(b) Suppose we had 24 balls i.e. n=24
so we the number of weighs needed are ceil[log3(24)] = 3 weighings.