Update: Red, White, Blue coin puzzle
I love my readers. Shortly after publishing my solution to the Red, White, Blue coin weighing puzzle, I received a charming email from Francis Fok about a more elegant solution. Because of the mutex states for the coins (one of the coins is heavier, and one lighter, or the other way around), there is just one bit of information for each colour set. As there are three sets, there are just 23 = 8 possibile combinations for how the coins could be configured. A weighing gives up 3 outcomes (left side down, balanced, right side down), so with two weighings, this give 3 × 3 = 9 distinct indicators; this should be enough to uniquely identify each configuration (my original solution had a caveat that, whilst I correctly seperated the coins, in one case I was not able to identify which seperated pile contained the heavier coins. Francis's solution removes that limitation).
I asked Francis if he would write it up, and he graciously did, along with his proof. Thank you! I don't want to steal anymore of his thunder. Here is his excellent solution and write-up:
Francis Fok
After reading the article 'Red, White, Blue coin weighing puzzle’, Nick gave a simple and clear solution to the puzzle. Please refer to the original article about the background of the puzzle.
In short, there are 6 coins with two in red, two in white, and two in blue. In each pair of coloured coins, there is one coin that is slightly heavier. Given that all heavier coins have identical weights and all the light coins have identical weight, what is the minimum number of weightings to separate the coins into two sets? We have a sensitive balance beam in help to solve the puzzle.
Nick gave a solution with 2 weightings that can separate coins into two sets. And his solution could also name those two sets in 75%. Thus, there is 25% we don't know which set is heavier. Could we also achieve 100% name two sets? Suppose it could not be done, could we prove it does not exist?
We stick to using the notation upper case letters are heavier coins and lower case letters are lighter coins. To simplify the discussion in the following, we order the coins by color sequence red, white, and blue. There are 8 possibles of weight configurations:
| Case | 1st coin | 2nd coin | 3rd coin | 4th coin | 5th coin | 6th coin |
|---|---|---|---|---|---|---|
| 1 | r | R | w | W | b | B |
| 2 | r | R | w | W | B | b |
| 3 | r | R | W | w | b | B |
| 4 | r | R | W | w | B | b |
| 5 | R | r | w | W | b | B |
| 6 | R | r | w | W | B | b |
| 7 | R | r | W | w | b | B |
| 8 | R | r | W | w | B | b |
Advertisement:
Analysis for 1st weighting
We could place at most 3 coins on each side of the balance beam. There would be three possible outcomes:
- Left is lighter ( < )
- Balance ( = )
- Right is lighter ( > )
There is a symmetry in colors, we take Red < White < Blue for solving tires. And those color patterns are the genotype in this part of analysis.
One coin on each side
When two coins are the same color, there would be only two possible outcomes as there is no way to have balance. We could divide all 8 cases by result into a 4-4 combination.
When two coins are different colors, there would be three possible outcomes. We could divide all 8 cases by result into a 4-2-2 combination.
List the result by a table:
| Case captured | ||||
|---|---|---|---|---|
| Color genotype | Coins to take | Left is lighter | Balance | Right is lighter |
| Red — Red | 1st — 2nd | 1,2,3,4 | 5,6,7,8 | |
| Red — Blue | 1st — 3rd | 3,4 | 1,2,7,8 | 5,6 |
Two coins on each side
By pigeon hole principle, there must be two coins that are the same color. Without loss of generality, the duplicated color is Red.
There are 4 different genotypes:
- Red, Red — White, White
- Red, Red — White, Blue
- Red, White — Red, White
- Red, White — Red, Blue
It is easy to see that the 1st way gives no hints about the weight of any coins because it always gives a balanced result.
| Case captured | ||||
|---|---|---|---|---|
| Color genotype | Coins to take | Left is lighter | Balance | Right is lighter |
| Red,Red — White,White | 1st,2nd — 3rd,4th | 1,2,3,4,5,6,7,8 | ||
| Red,Red — White,Blue | 1st,2nd — 3rd,5th | 4,8 | 2,3,6,7 | 1,5 |
| Red,White — Red,White | 1st,3rd — 2nd,4th | 1,2 | 3,4,5,6 | 7,8 |
| Red,White — Red,Blue | 1st,3rd — 2nd,5th | 1,2,4 | 3,6 | 5,7,8 |
Three coins on each side
When there are the same color coins on one side, there would also be the same color coins on the other side. And hence the weighting is canceled out and the case would degenerate to one coin on each side. Therefore, we only need to consider all three coins on the same side are different colors.
| Case captured | ||||
|---|---|---|---|---|
| Color genotype | Coins to take | Left is lighter | Balance | Right is lighter |
| Red,White,Blue — Red,White,Blue | 1st,3rd,5th — 2nd,4th,6th | 1,2,3,5 | 4,6,7,8 | |
Summary
Suppose there are 4 cases that we need to divide in the next weighing, there will be at least 2 cases that will lead to the same weighting result as there are at most 3 different weighting results. Therefore, it is a necessary condition that the max size of the divided cases be smaller or equal to 3 such that the puzzle could be solved in 2 weightings.
| Case captured | |||||
|---|---|---|---|---|---|
| Color genotype | Coins to take | < | = | > | Max size |
| Red — Red | 1st — 2nd | 1,2,3,4 | 5,6,7,8 | 4 | |
| Red — Blue | 1st — 3rd | 3,4 | 1,2,7,8 | 5,6 | 4 |
| Red,Red — White,White | 1st,2nd — 3rd,4th | 1,2,3,4,5,6,7,8 | 8 | ||
| Red,Red — White,Blue | 1st,2nd — 3rd,5th | 4,8 | 2,3,6,7 | 1,5 | 4 |
| Red,White — Red,White | 1st,3rd — 2nd,4th | 1,2 | 3,4,5,6 | 7,8 | 4 |
| Red,White — Red,Blue | 1st,3rd — 2nd,5th | 1,2,4 | 3,6 | 5,7,8 | 3 |
| Red,White,Blue — Red,White,Blue | 1st,3rd,5th — 2nd,4th,6th | 1,2,3,5 | 4,6,7,8 | 4 | |
There is only 1 genotype that fits the necessary condition. It is ‘Red, White — Red, Blue'.
Strategy
Weighting 1st and 3rd on the left against 2nd and 5th coin on the right.
When the result is balanced, only 2 cases are left:
| Case | 1st coin | 2nd coin | 3rd coin | 4th coin | 5th coin | 6th coin |
|---|---|---|---|---|---|---|
| 3 | r | R | W | w | b | B |
| 6 | R | r | w | W | B | b |
To classify these two cases, it is enough to weigh the 1st coin against the 2nd coin to separate two cases. (Of course, weighting the 1st coin against the 3rd coin is also ok. But weighing the 3rd coin against the 6th coin gives no help.)
Weighting the 1st coin against the 2nd coin:
- When 1st < 2nd, it captures the case 3.
- When 1st > 2nd, it captures the case 6.
When the left is lighter, only 3 cases are left:
| Case | 1st coin | 2nd coin | 3rd coin | 4th coin | 5th coin | 6th coin |
|---|---|---|---|---|---|---|
| 1 | r | R | w | W | b | B |
| 2 | r | R | w | W | B | b |
| 4 | r | R | W | w | B | b |
Weighting the 3rd coin against the 6th coin:
- When 3rd < 6th, it captures the case 1.
- When 3rd = 6th, it captures the case 2.
- When 3rd > 6th, it captures the case 4.
When the right is lighter, only 3 cases are left:
| Case | 1st coin | 2nd coin | 3rd coin | 4th coin | 5th coin | 6th coin |
|---|---|---|---|---|---|---|
| 5 | R | r | w | W | b | B |
| 7 | R | r | W | w | b | B |
| 8 | R | r | W | w | B | b |
Weighting the 3rd coin against the 6th coin:
- When 3rd < 6th, it captures the case 5.
- When 3rd = 6th, it captures the case 7.
- When 3rd > 6th, it captures the case 8.
As we could identify the coin weight configuration by 2 weightings, we could name two separated sets in 100%.
Static or Dynamic
Comparing Nick's solution and the solution shown in the above without considering the naming of sets. Nick’s solution is a static solution as the 1st and the 2nd weightings are independent. Thus, two weightings could swap and give the same solution. However, the solution shown in the above is dynamic: the selection of coins of the 2nd weighting depends on the result of the 1st weighting. Could we also have a static solution?
As both weightings could be the 1st weighting, both weighting patterns must be (color1, color2 -- color1, color3). We need to replace the word genotype by pattern. It is because the same color pattern selected with different coins selected gives different cases captured in nature.
| Case captured | ||||
|---|---|---|---|---|
| Color pattern | Coins to take | Left is lighter | Balance | Right is lighter |
| Red,White — Red,Blue | 1st,3rd — 2nd,5th | 1,2,4 | 3,6 | 5,7,8 |
| Red,White — Red,Blue | 1st,3rd — 2nd,6th | 1,2,3 | 4,5 | 6,7,8 |
| Red,White — Red,Blue | 1st,4th — 2nd,5th | 2,3,4 | 1,8 | 5,6,7 |
| Red,White — Red,Blue | 1st,4th — 2nd,6th | 1,3,4 | 2,7 | 5,6,8 |
| White,Red — White,Blue | 3rd,1st — 4th,5th | 1,2,6 | 4,5 | 3,7,8 |
| White,Red — White,Blue | 3rd,1st — 4th,6th | 1,2,5 | 3,6 | 4,7,8 |
| White,Red — White,Blue | 3rd,2nd — 4th,5th | 2,5,6 | 1,8 | 3,4,7 |
| White,Red — White,Blue | 3rd,2nd — 4th,6th | 1,5,6 | 2,7 | 3,4,8 |
| Blue,Red — Blue,White | 5th,1st — 6th,3rd | 1,3,7 | 4,5 | 2,6,8 |
| Blue,Red — Blue,White | 5th,1st — 6th,4th | 1,3,5 | 2,7 | 4,6,8 |
| Blue,Red — Blue,White | 5th,2nd — 6th,3rd | 3,5,7 | 1,8 | 2,4,6 |
| Blue,Red — Blue,White | 5th,2nd — 6th,4th | 1,5,7 | 3,6 | 2,4,8 |
Before finding a solution in the sea, we could eliminate some coins to take without removing all solutions. The arguments are:
- Without loss of generality, (1st, 3rd — 2nd, 5th) is selected as the 1st weighting. Then, all color patterns in (Red, White — Red, Blue) cannot be selected as 2nd weighting. It is because the intersection of both ‘Left is lighter’ must have 2 elements. Thus, eliminated all red colored rows.
- As White and Blue are symmetry in the 2nd weighting as taking (Red, White — Red, Blue) in the 1st weighting. Thus, eliminated all blue colored rows.
By observation, (3rd, 2nd -- 4th, 5th) could be used such that it provides a perfect match to (1st, 3rd -- 2nd, 5th). When the cases are in the same group in the 1st weighting (say cases 1 and 2), those cases must be in a different group in the 2nd weighting (case 1 is balanced while case 2 is in left is lighter).
Then the static strategy with 100% name the separated sets are as follows:
- Weight the 1st coin and 3rd coin on the left against 2nd coin and 5th coin on the right.
- Weight the 3rd coin and 2nd coin on the left against 4th coin and 5th coin on the right.
And the table of results:
| 1st weighting result | ||||
|---|---|---|---|---|
| < | = | > | ||
| 2nd weighting result | < | 2 | 6 | 5 |
| = | 1 | 8 | ||
| > | 4 | 3 | 7 | |