Sir Arthur de Templar was paid 27 gold coins for the infor- mation he provided on the last known location of the Holy Grail. Soon, from highly trusted sources, he learned that one of the 27 gold coins is fake. It has some mixture of iron and copper and hence its weight differs, meaning it is either lighter or heavier than a real gold coin. Sir Arthur paid a visit to his closest friend drug-maker Mr. Drugless and in a few seconds they identified the fake coin. Legend says that they used just an old weighing device of Mr. Drugless

(depicted in figure below) and could identify the fake coin in only 4 weighings. Recall that the fake coin maybe lighter or heavier (that is unknown) than the true-gold one.

(a) Repeat the procedure used by Sir Arthur de Templar and Mr. Drugless for identifying the fake coin among 27 gold coins in just 4 weighings.

(b) Extend it to an algorithm for identifying a single fake coin among N given gold coins using a minimum number of weighings. How many weighings do you need?

Note that a weighing is an operation of putting k coins on one plate of the device and k other coins on the other plate, where k=1,2,3,..., and checking if the device is in equilibrium, and if not, which plate is heavier/lighter.