1. Identifying a fake coin. There are n coins c1,02,.. .cn. Of these n coins, n 1 are genuine and one is fake. All the genuine coins have the same weight; the fake coin is lighter or heavier. A genie is present to help you figure out which coin is fake. You're allowed to put some coins on his left hand, another set of coins on his right hand. He will tell you if the two sets of coins have equal weight or not. Now he gets grumpy when you make too many weighings so your goal is to come up with a procedure that identifies the fake coin in as few weighings as possible. Here's a simple procedure for finding the fake coin in the case when n 3: First, put ci on the genie's left hand and c2 on his right hand. If their weights are equal, C3 is the fake coin. If their weights are not equal, compare c1 and C3. If their weights are equal, C2 is the fake coin; otherwise, c is the fake coin. This procedure identifies the fake coin in 2 weighings a. When n -9, describe a procedure that would identify the fake coin using as few weighings as possible in the worst case. Generalize your procedure to an arbitrary n. How many weighing are needed by your procedure in the worst case? Your answer should of course be in terms of n! b. Suppose the genie decides to be nicer. When the sets of coins on his left and right hands have different weights, he will tell you which set is heavier. How might you utilize this additional information to identify the fake coin faster? When there are n coins, how many weighings will your procedure make in the worst case? 1. Identifying a fake coin. There are n coins c1,02,.. .cn. Of these n coins, n 1 are genuine and one is fake. All the genuine coins have the same weight; the fake coin is lighter or heavier. A genie is present to help you figure out which coin is fake. You're allowed to put some coins on his left hand, another set of coins on his right hand. He will tell you if the two sets of coins have equal weight or not. Now he gets grumpy when you make too many weighings so your goal is to come up with a procedure that identifies the fake coin in as few weighings as possible. Here's a simple procedure for finding the fake coin in the case when n 3: First, put ci on the genie's left hand and c2 on his right hand. If their weights are equal, C3 is the fake coin. If their weights are not equal, compare c1 and C3. If their weights are equal, C2 is the fake coin; otherwise, c is the fake coin. This procedure identifies the fake coin in 2 weighings a. When n -9, describe a procedure that would identify the fake coin using as few weighings as possible in the worst case. Generalize your procedure to an arbitrary n. How many weighing are needed by your procedure in the worst case? Your answer should of course be in terms of n! b. Suppose the genie decides to be nicer. When the sets of coins on his left and right hands have different weights, he will tell you which set is heavier. How might you utilize this additional information to identify the fake coin faster? When there are n coins, how many weighings will your procedure make in the worst case