AdministratorJune 17, 2020 at 3:28 pm
You have 15 identical coins – 2 of them made of pure gold and the other 13 made of nickel (covered with thin gold layer to mislead you). You also have a gold detector, with which you can detect if in any group of coins, there is at least one gold coin or not. How can you find the pure gold coins with only 7 uses of the detector?
Puzzle from the archives.
AdministratorJune 17, 2020 at 3:57 pm
The solution is provided HERE. Some notes regarding the solving process…
The main idea is that if we have X measurements and there are Y combinations for the identities of the gold balls, then Y ≤ 2ˣ.
First, we note that in order to find 2 gold balls, we need:
- 4 measurements for a group of 5
- 5 measurements for a group of 6
- 5 measurements for a group of 7
We can also see that we need at least 6 measurements for a group of 8. Indeed, if we measure 1 or 2 balls on our first try and there are no gold balls among them, then we will end up with 6 balls and only 4 measurements. If we measure 3 balls on our first try and there are gold balls among them, then there are at least 3 + 3 × 5 = 18 combinations for the identities of the gold balls, so 4 measurements would not be enough.
For 11 balls, with similar considerations, we can see that there are at least 7 measurements needed.
To solve the problem with 15 balls, we see that we need to measure exactly 5 balls on our first try. Otherwise, if we measure 4 balls or less and none of them is gold, then we will end up with 11 balls and only 6 measurements. If we measure 6 balls or more and there are gold balls among them, then there are at least 6 × 5 / 2 + 6 × 9 = 69 combinations for the identities of the gold balls, so 6 measurements would not be enough.
If there are no gold balls in the group of 5, then we reduce the problem to 2 gold balls in a group of 10, with 6 measurements. It is not hard to finish the solution from here.
If there are gold balls in the group of 5, then there are 5 × 4 / 2 + 5 × 10 = 60 combinations for the identities of the gold balls. This is very close to 2⁶ = 64, so the main idea above makes it easy to filter out all measurements that would not lead to a correct solution.
MemberJune 18, 2020 at 7:06 am
Did you mean Y ≤ 2ˣ ?
Is this formula true for n gold balls?
AdministratorJune 18, 2020 at 8:28 am
You are correct, it should be Y ≤ 2ˣ, where X is the number of measurements (e.g. 7 at the start), and Y is the number of combinations (e.g. 15 * 14 / 2 = 105 at the start). The number 2 here comes from the observation that every measurement has 2 outcomes – YES and NO.
For example, in the famous problem with the 9 balls and 1 heavier, the formula is Y ≤ 3ˣ, where X = 2 is the number of measurements, and Y = 9 is the number of possibilities for the heavier ball. Here we have the number 3 instead of 2 because each use of the scale measurements gives 3 outcomes – LEFT SIDE HEAVIER, RIGHT SIDE HEAVIER, or THE TWO SIDES EQUAL.
To see why the formula is correct, notice that every measurement splits the set of possibilities (for the location of the gold balls) into 2, not necessarily equal size, parts. Thus, if every time we get unlucky and we are left with the larger possibility subset, after X measurements, we will be left with more than 1 possibility, and won’t be able to conclude with certainty which ones the gold balls are.
MemberJune 18, 2020 at 7:27 am
According to your analysis, we can solve the problem when there are 16 coins, with 7 steps?
AdministratorJune 18, 2020 at 8:33 am
The formula goes only one way. If the inequality is violated, then you know for sure that you can’t find the gold balls with X measurements. However, it is possible that the inequality is satisfied and you still can’t find the gold balls.
MemberJune 18, 2020 at 8:44 am
Thank you for your explanation ❤