1

The fake coin is defined by either having a lesser or greater weight than all of the other coins in the problem.

Say there are 12 coins, 1 out of the 11 which is the fake coin. How does everyone know to start off by initially weighing 4 coins against 4 coins? Why not 6 against 6 (since there are 12)? Why not 1 against 1, 2 against 2, or 3 against 3 either? Why is it general consensus that 4 coins against 4 coins is the optimal initial weighing?

Same thing if the problem were to have 8 coins, 1 of which were the fake. How does everyone conclude to initially weigh 3 coins against 3? Why not 4 against 4, 1 against 1, or 2 against 2?

There must be logic behind determining the initial weighing?

user3451821
  • 57

1 Answers1

0

For each weighing, there are three possible outcomes. Thus, N weighings can yield $ 3^N$ outcomes.

The fake coins is one of 12, and it can be heavy or light (2 possibilities), so you have a total of 24 possible answers. You must break that into 3 groups of not more than 9 each in the first weighing.

If you put 6 on each side, then you have zero possible answers for the scale to come up balanced, which means 24/2 = 12 for each direction, left or right. 12 is more than you can differentiate in two more weighings, so that won't work. Similarly, if you put 5 on each side, there are 4 possible answers where the scale is even and (24-4)/2 = 10 for the scale to tilt either direction. 10 is also too many.

If you put 4 on each side, that leaves for unweighted, so there are 4x2=8 possible answers where the scale is balanced and (24-8)/2=8 possible answers for it to tilt either direction. These are all $\leq$ 9, so each of them should work.

Then, for each combination, you need to break up the 8 possible answers to three groups of not more than 3 each, so your third weighing can find the final answer.

This general logic: break the set of answers up into 3 groups of nearly equal size, is the path to solutions for almost all weighing problems.

<

user3294068
  • 1,272
  • Are you saying that it is a full 3-art decision tree? If so I don't follow because at some points, it is impossible for there to be a balance (when it nears the end). Or do you just mean for the initial weighing? – user3451821 Apr 07 '14 at 18:12
  • It is not a full tree, no. There are only 24 possibilities, while a full tree would have 3^3 = 27. The goal at each step is to make sure that each group you divide down to has no more than 3^i possible answers in it (when i steps remain), or else you won't be able to solve the problem. So first pass: each group has <= 9 answers. Second pass, each group must have <= 3 answers. – user3294068 Apr 07 '14 at 20:21