Lighter or heavier? You have n > 2 identical-looking coins and a two-pan balance

Question

Lighter or heavier? You have n > 2 identical-looking coins and a two-pan balance scale with no weights. One of the coins is a fake, but you do not know whether it is lighter or heavier than the genuine coins, which all weigh the same. Design a (1) algorithm to determine whether the fake coin is lighter or heavier than the others.

Eight-queens problem Consider the classic puzzle of placing eight queens on an 8 × 8 chessboard so that no two queens are in the same row or in the same column or on the same diagonal. How many different positions are there so that a. no two queens are on the same square? b. no two queens are in the same row? c. no two queens are in the same row or in the same column? Also estimate how long it would take to find all the solutions to the problem by exhaustive search based on each of these approaches on a computer capable of checking 10 billion positions per second.

Explanation / Answer

Q1) Algorithm goes as follow :

For eg: N = 7 , we can form groups of 2 , 2 , 2 with 1 coin as leftover. Now we can compare the weight of three groups. Suppose group1 was heavier than other two groups , this means the fake coin is in group1 and also the fake coin is heavier. Else if all the three groups have the same weight, that means the fake coin was the one which was leftover.

If N = 8 , we can from groups of 2 , 2 , 2 with 2 coins as leftover. Again we compare the groups to check if teh faulty coin lies there same as the previous example. If not then we know that faulty coin is one of the leftover ones. So we take out 1 coin from the pure coins and we have two leftover coins. Now we pairwise compare these three coins. If one coin is heavier than other two it means it is the faulty one and is heavier and same in case the faulty coin is lighter.

Q2)

For every case total number of postion checks required = 0(place the first queen anywhere) + 1(check if second queen attacks first ) + 2(check if third attacks first and second)....7 = 28.

The above algorithms are based on the assumption that we keep track of the already placed queens and therefore the above algorithms do not require any backtracking. Basically we are only producing valid arrangements.

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.