Weighing Coins during the Mystery Hunt
The ultimate goal of each MIT Mystery Hunt is to find a hidden coin. So it was highly appropriate that our 2013 team created a coin-weighing puzzle (written by Ben Buchwald, Darby Kimball, and Glenn Willen) as a final obstacle to finding the winning coin:
There are nine coins, one real and eight fake. Four of the fake coins weigh the same and are lighter than the real coin. The other four fake coins weigh the same and are heavier than the real coin. Find the real coin in seven weighings on the balance scale.
Actually, it is possible to find the real coin in six weighings. Can you do that?
Share:
Olaf Hansen:
I think I can do it. But I can’t describe my method in a mathematically elegant way, as I have attacked the problem inductively, trying for each weighing to take all possible combinations into account, and extract as much information as possible. (I am not a real mathematician, so this is my only tool)
1) First I make two groups of 4 coins, the last coin, I put in my pocket.
2) I then weigh the two groups against each other. (First weighing)
3) After that, I make two new groups of 4 coins, by taking 2 coins from the first of the original groups, and switching them with two coins from the other group.
4) I then weigh the new groups against each other. (Second weighing)
If any of these groups weigh the same its trivial, because then I have the real coin in my pocket. If this is not the case, I separate the coins into 4 groups of 2 coins:
-Two coins have been in the heavier group twice, I call them “pair 1”.
-Two coins have been heavy group in the first weighing, and in the light group in the second weighing. I call them “pair 2”.
-Two coins have been in the light group in the first weighing, and in the heavy group in the second weighing. I call them “pair 3”.
-Finally, two coins have been in the lightest group twice, I call them “pair 4”.
5) I now group pair 1 and pair 4, and weigh them against pair 2 and pair 3 as a group. (Third weighing).
This will result in 3 different cases:
CASE 1: The two groups in the third weighing, weighs the same. This is again trivial, as I will have the real coin in my pocket. If this is not the case, I know for sure that the coin in my pocket is not the real one, as it would have been revealed by now….
CASE 2: Pair 1 is also part of the heavy group in the third weighing.
In this case, I continue by weighing pair 3 against pair 4. (Fourth weighing) This results in two sub cases:
a) Pair 3 and pair 4 have equal weight.
Here I continue by weighing pair 2 against pair 4. (Fifth weighing) Now:
– If pair 2 and 4 has equal weight, then the real coin is in pair 1 together with a heavy coin.
– If pair 2 is heavier than pair 4, then the real coin is in pair 2 together with a heavy coin.
– If pair 4 is heavier than pair 2, then the real coin is in pair 2 together with a light coin.
By weighing the coins in the relevant pair against each other, I can now determine the real coin in the sixth weighing.
b) Pair 3 and pair 4 have different weights.
If this is the case, I take the heavier of the two pairs, and weigh it against pair 2. (Fifth weighing) Now:
– If this pair is heavier than pair 2, then the real coin is in pair 2 together with a light coin.
– If pair 2 is heaviest, then the real coin is in the pair together with a light coin.
By weighing the coins in the relevant pair against each other, the real coin will reveal itself as the heaviest in the sixth weighing.
CASE 3: Pair 1 is part of the lighter group in the third weighing.
In this case, I can be sure, that pair 4 consists of two light coins. I continue by weighing pair 2 against pair 3. This results in three sub cases:
a) Pair 2 and pair 3 have equal weights.
The real coin is in pair 1, but I don’t if it is together with a light coin or a heavy coin. I take one of the light coins of pair 4, and switch it with one of the coins in pair 3 (or 2). Then I weigh this pair against pair 1. Now:
– If pair 1 is heaviest, then the real coin is in pair 1 together with a heavy coin.
– If pair 1 is lighter, then the real coin is in pair 1 together with a light coin.
The real coin can now be revealed by weighing the coins of pair 1 against each other in the sixth weighing.
b) Pair 3 is heavier than pair 2.
In this case pair 3 consists of two heavy coins, and I can make a heavy-light pair, by switching one of the heavy coins of pair 3 with one of the light ones of pair 4. I then weigh the heavy-light pair against pair 2. (Fifth weighing) Now:
– If the two pairs has equal weight, then the real coin is in pair one together with a heavy coin.
– If pair 2 is heavier, then the real coin is in pair two together with a heavy coin.
– If pair 2 is lighter, then the real coin is in pair two together with a light coin.
Again the real coin can be revealed by weighing the coins in the relevant pair against each other in the sixth weighing.
c) Pair 2 is heavier than pair 3.
Here I take the coin from my pocket, and add it to pair 1. Then I take one of the light coins from pair 4 and add it to pair 2. (I keep track of the coins, so I can reconstruct the original pairs) Then I weigh the two groups of three coins against each other.
(Fifth weighing) Now:
If the two groups weigh the same, then the real coin is in pair 3 together with a light coin.
If the group containing pair 1 is heavier, then the real coin is in pair 2 together with a heavy coin.
If the group containing pair 1 is lighter, then the real coin is in pair 1 together with a heavy coin.
Again the real coin can be revealed by weighing the coins in the relevant pair against each other in the sixth weighing.
Unless I have missed something (which is a real possibility), I think this procedure should do the trick….
PS: Thank you Tanya for a entertaining site.
2 March 2013, 8:34 amOlaf Hansen:
Forget it, I just realized, that I overlooked some combinations..
2 March 2013, 1:55 pmOlaf Hansen:
This one is better, I think.
First I make three groups of three coins. Group 1 consists of the coins a, b, and c. Group 2 consists of coins d, e, and f. Group 3 consists of coins g, h and i.
Then I take a coin from group 1 and weigh it against a coin from group 2. I’ll notice which coin is heavier, or if the coins have equal weight. For convenience I will also switch the coins, so that the heavier coins go to group 1, while the lighter ones go to group 2. If two coins have equal weight, one coin goes to each group. I do this with all of the coins from group 1 and 2 (three weightings). By now a coin from group 2 is never heavier than a coin from group 1.
After the three weightings, I have four cases:
CASE 1: In all three weightings one coin was heavier than the other.
Group 1 (a,b,c) consists of the heavier coins from the three weightings
Group 2 (d,e,f) consists of the light coins from the three weightings
Group 3 (g,h,i) consists of the coins that have not been weighed yet.
I then weigh a+d against g+h, and b+e against h+i. Now:
a) If a+d = g+h and b+e = h+i, then I weigh c+f against g+i.
– If c+f turns out to be heavier than g+i, then the real coin is f.
– If g+i is heavier than c+f, then the real coin is c.
b) If a+d > g+h and b+e > h+i, then I weigh d against e. The heavier is the real coin.
c) If a+d < g+h and b+e g+h and b+e < h+i or a+d h+i, then the real coin is h.
e) If a+d = g+h and b+e > h+i, then I weigh e against f.
If one coin is heavier, then it is the real coin. Otherwise, the real coin is i.
f) If a+d = g+h and b+e < h+i, then I weigh b against c.
If one coin is lighter, then it is the real coin. Otherwise, the real coin is i.
If a+d g+h and b+e = h+i, the method is like in e) or f). I will not repeat it.
Case 2: In one of the weightings, the coins weighed the same.
In this case, I’ll start by rearranging the coins (if necessary), so that the coins of equal weight becomes “a” and “d”. Then I weigh a+b+c against g+h+i. now:
a) If a+b+c = g+h+i, then I weigh e against f. The heavier of the two is the real coin.
b) If a+b+c < g+h+i, then I weigh b+e against c+f.
– If b+e = c+f, then group 3 consists of the real coin together with two heavy coins. I can then find the real coin by weighing two of the coins from group 3 against each other.
– If b+e c+f, the real coin is c.
c) If a+b+c >g+h+i, then again I weigh b+e against c+f.
– If b+e = c+f, then group 3 consists of the real coin together with two light coins. I then find the real coin, for instance by weighing g against h.
– If b+e c+f, then again I weigh d+e+f against g+h+i. If the two groups have equal weight, then the real coin is c. Otherwise, the real coin is e.
Case 3: In two of the weightings, the coins weighed the same.
I’ll start by rearranging the coins (if necessary), so that the coins a,d and b,e becomes the coins with equal weight. Then I’ll weigh c+f against g+h, and c+f against h+i. Now:
a) If c+f is heavier in both weightings, I weigh a+b against c+f.
– If a+b c+f, then the real coin is c.
b) If c+f is lighter in both weightings, again I weigh a+b against c+f.
– If a+b c+f, then the real coin is c.
c) Otherwise:
– If c+f = g+h, the real coin is i.
– If c+f = g+h, the real coin is i.
– If c+f = h+i, the real coin is g.
– If c+f = h+i, the real coin is g
– If c+f h+i, the real coin is h.
– If c+f > g+h and c+f < h+i, the real coin is h.
Case 4: The coins had equal weight in all three weightings.
In this case, the real coin is in group three together with two light coins or two heavy coins. I weigh the coins of group 3 against each other, until I find two coins of equal weight. Then the real coin is the third one. I will take no more than three weightings.
7 March 2013, 8:42 pmOlaf Hansen:
Ps: actually a coin from group 2 can be heavier than one from group 1. I wasn’t thinking while I wrote this. The rest is OK though (at least I think so)….
7 March 2013, 8:48 pmolaf hansen:
I should have been more precise. What I meant was: I weigh a against d, and reaarange if necessary. Then I weigh b against e and do the same, and finally I follow same procedure for c against f. Now d is never heavier than a, e is never heavier than b, etc…
7 March 2013, 9:24 pmAnimesh:
I don’t think groups need to be made.
Pick up any two random coins. Depending on the result heavier or lighter….we can again pick another coin and keep eliminating. A rough sketch might be
Let’s say I had picked up ( assume L = Lighter, H = Heavier , F = Fair)
a–> L and b–>F…first weighing I know b > a…
Still this doesn’t give me enough info…again I pick another one….say H..and do two weighings
Case 1…if I had picked H….compare against a. If greater than both….I surely know I picked up H…and fair coin is b. Cant be both L…otherwise first weighing should have been equal.
Case 2. …if I had picked up L….will give a = L…and again I pick up another coin…to compare against b. Remember at this point I eliminated 2 coins. Both L’s. In max 6 moves…i can reach the solution
Might have missed something…..will verify again…but I think 6 cases are enough.
12 March 2013, 10:48 amTanya Khovanova:
My solution in 7 weighings.
First you divide in groups of three and find out their relative weights in 3 weigings. If two groups are equal then the third group is either LLR or HHR and the coin can be easily found. If not, in the next three weighings you can find out the relative weight of the coins in the middle group. If one of them is real fine. If not then the middle group is LLH (or HHL) and you know that. Then the real coin is in the lighter/heavier group and can be found in one weighing.
14 March 2013, 10:05 amReila:
Tanya,
It’s impossible to find the the real coin for certain in 6 weighings using your solution. The worst-case scenario would still be 7 weighings.
11 April 2013, 4:10 amPhilippe Fondanaiche:
Good morning,
It is possible to find the real coin in six weighings
We share the 9 coins in five lots, four lots A, B, C, D of 2 coins each + the ninth coin aside. Four successive weighings are carried out with a coin of each lot A, B, C, D against the second coin of the same lot.
If any of the weighings is balanced then the corresponding two coins of the lots are necessarily false and are of the type HH or LL
If instead one weighing is unbalanced, then the lot is of type HL or HR or RL
The four successive weighings provide five possible outcomes:
1) The four weightings are balanced. Therefore the real coin is the ninth one. Four weighings are enough.
2) Three weighings are balanced (A, B, C,WLOG) and the fourth is unbalanced (D). D is of the type (H,R) or (R,L) and the ninth coin is H or L. D necessarily contains the real coin and one weighing is enough to determine R. Five weighings in total.
3) Two weighings are balanced (A and B,WLOG) and the other two are unbalanced (C and D). We have A = (H,H) and B = (L, L) or vice versa. Therefore the possible configurations of C, D with the ninth coin are the following:
Lot C Lot D 9th coin
3-1) (H, R) (H, L) L
3-2) (H, L) (H, L) R
3-3) (H, L) (H, R) L
3-4) (H, L) (R, L) H
3-5) (R, L) (H, L) H
In the fourth weighing, the heavier coin of C is weighed against the 9th coin.
If the weighing is balanced, this is the 3-4 case and a fifth weighing provides the real coin in D.
If the weighing is unbalanced with RL or H> R, a fifth weighing is performed by comparing the lighter coin of D to the 9th coin and according to the three possible outcomes, the real coin is in C or is the 9th coin or is in D.
4) A weighing is balanced (A, WLOG) and three unbalanced weights are (B, C and D).
There are two possible cases:
4-1) A = (H, H), B = (H, L), C = H,L), D =(R,L) and 9th coin = L with two permutations of B, C and D
4-2) A = (L, L), B = (H, L), C =(H,L), D =(H, R) and 9th coin = H with two permutations of B, C and D
A fifth weighing allows to identify 4-1 or 4-2.Indeed in the case 4-1 the lighter coins of B, C and D and the 9th coin are all L while in the case 4-2 the lighter coins and the 9th coin are of the types H,L and R. So we take these 4 coins and we compare two coins against the other two. If equal, this is the 4-1 case. If unbalanced, this is the case 4-2
A sixth weighing allows to identify R.Indeed:
– In the case 4-1, we weigh the heavier coin of any of the three lots B, C or D against the heavier coin of another lot. If equal, the two coins are of type H and the real coin is in the third lot where it is the heavier. If unbalanced, the real coin is the lighter.
– In the case 4-2, we weigh the lighter coin of any of the three lots B, C or D against the lighter coin of another lot. If equal, the two coins are the type L and the real coin is in the third lot where it is the lighter. If unbalanced, the real coin is the heavier.
In both cases six weighings are enough.
5) The four weighings are unbalanced. We get three configurations in which the 9th piece is the type R ,H and L
1 May 2013, 8:13 am5-1) A = (H, H) , B = (H, L), C = (H, L), D = (H, L) and 9th coin = R
5-2) A = (H, H), B = (H, L), C = (H, L), D = (R, L) and 9th coin = H
5-3) A = (H,H), B = (H, L), C = (H, L), D = (H, R) and 9th coin = L
Given the permutations of A, B, C and D, there are a total of 1 + 4 + 4 = 9 possible configurations.
There are still two weighings and each one has three modes: balance (=), left pan heavier (>), left pan lighter ( <
(2,3,4)/(5,6,8) = = > < = < >
Philippe Fondanaiche:
Good morning,
It is possible to find the real coin in six weighings
We share the 9 coins in five lots, four lots A, B, C, D of 2 coins each + the ninth coin aside. Four successive weighings are carried out with a coin of each lot A, B, C, D against the second coin of the same lot.
If any of the weighings is balanced then the corresponding two coins of the lots are necessarily false and are of the type HH or LL
If instead one weighing is unbalanced, then the lot is of type HL or HR or RL
The four successive weighings provide five possible outcomes:
1) The four weightings are balanced. Therefore the real coin is the ninth one. Four weighings are enough.
2) Three weighings are balanced (A, B, C,WLOG) and the fourth is unbalanced (D). D is of the type (H,R) or (R,L) and the ninth coin is H or L. D necessarily contains the real coin and one weighing is enough to determine R. Five weighings in total.
3) Two weighings are balanced (A and B,WLOG) and the other two are unbalanced (C and D). We have A = (H,H) and B = (L, L) or vice versa. Therefore the possible configurations of C, D with the ninth coin are the following:
Lot C Lot D 9th coin
3-1) (H, R) (H, L) L
3-2) (H, L) (H, L) R
3-3) (H, L) (H, R) L
3-4) (H, L) (R, L) H
3-5) (R, L) (H, L) H
In the fourth weighing, the heavier coin of C is weighed against the 9th coin.
If the weighing is balanced, this is the 3-4 case and a fifth weighing provides the real coin in D.
If the weighing is unbalanced with RL or H> R, a fifth weighing is performed by comparing the lighter coin of D to the 9th coin and according to the three possible outcomes, the real coin is in C or is the 9th coin or is in D.
4) A weighing is balanced (A, WLOG) and three unbalanced weights are (B, C and D).
There are two possible cases:
4-1) A = (H, H), B = (H, L), C = H,L), D =(R,L) and 9th coin = L with two permutations of B, C and D
4-2) A = (L, L), B = (H, L), C =(H,L), D =(H, R) and 9th coin = H with two permutations of B, C and D
A fifth weighing allows to identify 4-1 or 4-2.Indeed in the case 4-1 the lighter coins of B, C and D and the 9th coin are all L while in the case 4-2 the lighter coins and the 9th coin are of the types H,L and R. So we take these 4 coins and we compare two coins against the other two. If equal, this is the 4-1 case. If unbalanced, this is the case 4-2
A sixth weighing allows to identify R.Indeed:
– In the case 4-1, we weigh the heavier coin of any of the three lots B, C or D against the heavier coin of another lot. If equal, the two coins are of type H and the real coin is in the third lot where it is the heavier. If unbalanced, the real coin is the lighter.
– In the case 4-2, we weigh the lighter coin of any of the three lots B, C or D against the lighter coin of another lot. If equal, the two coins are the type L and the real coin is in the third lot where it is the lighter. If unbalanced, the real coin is the heavier.
In both cases six weighings are enough.
5) The four weighings are unbalanced. We get three configurations in which the 9th piece is the type R ,H and L
5-1) A = (H, H) , B = (H, L), C = (H, L), D = (H, L) and 9th coin = R
5-2) A = (H, H), B = (H, L), C = (H, L), D = (R, L) and 9th coin = H
5-3) A = (H,H), B = (H, L), C = (H, L), D = (H, R) and 9th coin = L
Given the permutations of A, B, C and D, there are a total of 1 + 4 + 4 = 9 possible configurations.
There are still two weighings and each one has three modes: balance (=), left pan heavier (>), left pan lighter ( <
(2,3,4)/(5,6,8) = = > < = < >
The table is read as follows: if the results of the 5th and 6th weighings are (), it is numbered 4 … etc.
1 May 2013, 8:16 amPhilippe Fondanaiche:
The fifth paragraph was incomplete:
5) The four weighings are unbalanced. We get three configurations in which the 9th piece is the type R ,H and L
1 May 2013, 8:23 am5-1) A = (H, H) , B = (H, L), C = (H, L), D = (H, L) and 9th coin = R
5-2) A = (H, H), B = (H, L), C = (H, L), D = (R, L) and 9th coin = H
5-3) A = (H,H), B = (H, L), C = (H, L), D = (H, R) and 9th coin = L
Given the permutations of A, B, C and D, there are a total of 1 + 4 + 4 = 9 possible configurations.
There are still two weighings and each one has three cases: balance (=), left pan heavier (>), left pan lighter ( <
(2,3,4)/(5,6,8) = = > < = < >
The table is read as follows: if the results of the 5th and 6th weighings are (), it is numbered 4 … etc.
Philippe Fondanaiche:
It is impossible to send the decision table.Last try:
There are still two weighings and each one has three modes: balance (=), left pan heavier (>), left pan lighter ( <
1 May 2013, 8:35 am(2,3,4)/(5,6,8) = = > < = < >
The table is read as follows: if the results of the 5th and 6th are weighed (), it is numbered 4 … etc.
David Reynolds:
I have found a six weighing solution. I have also proven (via computer search) that five weighings are not sufficient to find the real coin in all cases.
3 July 2013, 5:09 pm