Problem

There are N identically looking coins one of which is fake. Assume that the fake coinis known to be lighter than the genuine ones. There is a balance scale but there areno weights; the scale can tell whether two sets of coins weigh the same and, if not,which of the two sets is heavier (but not by how much).

1. Design a brute-force algorithm (write a Python program) for detecting the fakecoin.

2. Design a decrease by constant and conquer algorithm (write a Python program) for detecting the fake coin.