S2T2

Jim Randell 9:33 am on 16 January 2022 Permalink Reply
Tags: by: W. E. Chapman ( 2 )   

• 

  Jim Randell 9:38 am on 16 January 2022 Permalink | Reply

  We have tackled similar problems before, see: Enigma 1589, Teaser 2500.

  For Enigma 1589 I wrote a constructive solution that searches for a minimal decision tree.

  For Teaser 2500 I gave a program that will construct minimal decision trees for a set of related problems.

  For a “type 1” problem (where we need to find the counterfeit coin, and determine if it is heaver or lighter), with n weighings we can deal with a set of (3^n − 3) / 2 coins.

  However, each decision tree for the “type 1” problem has a leaf that is impossible to reach if we are guaranteed that there is exactly one counterfeit coin. But if there are no counterfeit coins then every weighing balances and we reach the impossible leaf.

  So, for this type of puzzle (where we need to determine which coin is counterfeit, but not if it is heavier or lighter), we can put one of the coins aside and then proceed with the weighings for a “type 1” puzzle, if we reach the impossible leaf we know that it must be the unweighed coin that is counterfeit, and we don’t need to determine whether it is lighter or heavier, so we can stop. This means we can manage 1 extra coin compared to the “type 1” puzzle.

  So in n weighings we can deal with a set of (3^n − 1) / 2 coins. (The same as a “type 2” problem, where we have to determine the counterfeit coin, and whether it is lighter or heavier, but we have a reference coin available).

  Hence:

  With 6 weighings we can deal with a set of (3^6 − 1) / 2 = 364 coins.

  And with 9 weighings we can determine the counterfeit coin from (3^9 − 1) / 2 = 9841 coins.

  Solution: 364 coins require 6 weighings. With 9 weighings we can deal with up to 9841 coins.

  ---

  Note that the formula applies to n ≥ 2 weighings.

  A set consisting of 1 coin requires 0 weighings (as the set must contain a counterfeit coin), and with a set consisting of 2 coins it is not possible to determine which coin is counterfeit (unless we have a reference coin, or are told that the counterfeit is light (or heavy)).

  With 4 coins (1, 2, 3, 4) we can weigh 1 against 2. If they balance (and so are both good), we weigh one of these good coins against 3. If the second weighing balances, the counterfeit is 4. If it doesn’t balance, it is 3. If the initial weighing does not balance, then the counterfeit coin is 1 or 2, and 3 and 4 are good. So weigh 1 against 3. If they balance, the counterfeit is 2. If not the counterfeit is 1. So we can solve 4 coins with 2 weighings.

  ---

  The published solution (27th April 1952) is as follows: [link]

  Readers were posed the problem before a cashier having a pile of coins of which he knows one to be abnormal in weight, and a pair of scales but no other Instrument. They were asked (a) the least number of trial weighings he must make to be sure of identifying the abnormal coin in a pile of 364, and (b) the largest number of coins among which he may be sure of Identifying the abnormal one In nine “trials.” This was a highly successful brain-teaser in respect of the number of clever brains which it evidently teased. There were nearly 1,500 entries, but barely one in ten of them gave both answers correctly. Answers to (a) ranged from 6 to 16, and to (b) from 22 to 19,683.

  On the other hand, correct entrants had little success in expressing the method of trial succinctly. The clue is to start by weighing 121 against 121. If they balance, the remaining 122 include the abnormal coin; if not, the 122 are known to be all “good” coins. Combinations from the good and doubtful groups then reduce the scale of alternative third trials to 27 or 40, fourth to 9 or 13, fifth to 3 or 4, and sixth to one coin in each pan.

  The correct answers are: (a) 6, (b) 9,841. The latter follows the formula (3^n − 1) / 2 where n = the maximum number of trials; many entrants offered 3^n (giving the answer 19,683), which is demonstrably incorrect, e.g., for n=2.

  LikeLike