Yet Another Coin Weighing Problem
I got this problem from my friend, a middle-school math teacher, Tatyana Finkelstein.
We have N coins that look identical, but we know that exactly one of them is fake. The genuine coins all weight the same. The fake coin is either lighter or heavier than a real coin. We also have a balance scale.
Unlike in classical math problems where you need to find the fake coin, in this problem your task is to figure out whether the fake coin is heavier or lighter than a real coin. Your challenge is that you are only permitted to use the scale twice. Find all numbers N for which this can be done.
I would like to add an extra twist to the problem above. It is conceivable that there might be several different strategies for finding the direction in which the weight of the fake coin deviates from the real coins. In this case it is better to choose a strategy that can redeem as many coins as possible — that is, to identify the maximum number of coins as real.
The number of coins you identify as real depends on the outcomes of your weighings. Then what is the precise definition of the best strategy?
Let us call a strategy k-redeem if after the weighings you are guaranteed to demonstrate that k coins are real, but you are not guaranteed to demonstrate that k+1 coins are real. Your task is to analyze two-weighing strategies and choose the most profitable one — the strategy that guarantees to redeem the largest possible number of coins, that is, a k-redeem strategy for the largest k.
Share:
Aman Barot:
Its solvable for all N. Lets divide into three cases:
Numbers of the form 3k, 3k+1,3k+2.
Case 1:Weigh k-coins against k-coins in first move, and leftout k-coins against any of the earlier weighed k-coins.
Case 2:Separate out 1 coin, Now weigh any of k-coins against k-others, if they are unequal, then on next weighing weigh any of the k-coins from the already weighed and k-others from unweighed, and then, its done. If they are equal, take k+1 from these coins and weigh against leftout k+1 coins.
Case 3:Again, separate 2 coins and weigh k-coins against k-coins in first move, if unequalthen on next weighing weigh any of the k-coins from the already weighed and k-others from unweighed. If they are equal, take k+2 from these coins and weigh against leftout k+2 coins.
19 March 2010, 10:40 pmDaan:
Well, not for all N, I’d say. Take N=2; then one will be heavy and one will be light, but you have no way of telling which is real and which is fake.
20 March 2010, 3:25 amT.:
This can be considered as the classical weighing problem, but where instead of localizing down to one of the 2N possibilities, the task is to locate a set of up to S coins that contains the false coin, and determine whether the false coin is lighter or heavier. Here S is a given parameter, S=1 is the original N coins problem and S=N is the problem in the current posting.
As in the classical problem, if W weighings (of given sets of coins) provide enough information solve the problem, there are at most (3^W – 3)/2 possible outcomes of those weighings, which together with the factor of S ambiguity, has to be enough information to fully determine the false coin. In other words, the maximum number of coins that can be handled with W weighings is at most S*(3^W – 3)*(1/2) coins. For example, in 2 weighings we can reduce 15 coins down to one of 5 possibilities and determine light/heavy status of the false coin. The information bound may be attainable in all cases by following the classical (S=1) weighing schedule until ambiguity is reduced to S or fewer coins, but I have not tried to check whether this is really true.
23 March 2010, 4:01 pmTanya Khovanova:
Aman,
Your solution doesn’t work for several small N.
23 March 2010, 5:12 pmRahul Singal:
According to me, this is possible for all N=4k, k=1,2,3,4…..
Divide the N coins equally so that we have two bundles of N/2 coins each.
Assume that the fake coin is lighter.
Now take the two bundles on the balance and take the bundle which is heavier(as according to our assumption this bundle will contain all the real coins).
Now take this particular bundle and divide it as N/4 coins equally and weigh it on a balance.
If they are equal, our assumption was correct otherwise the fake coin is heavier.
31 March 2010, 5:39 amT.:
Rahul, that strategy is not optimal in the sense that Tanya was asking about: minimizing the size of the set to which we know the unknown coin belongs. If you start out with N coins and have two weighings, you should be able to reduce to a set of size N/3 (but no smaller than this) in addition to determining light/heavy status of the coin. Your strategy reduces the ambiguity only to N/2 if the second weighing result is “equal”.
It is clear that N/3 (more precisely Ceiling(N/3)) is possible. Given 3k coins, divide into 3 groups of k.
9 April 2010, 12:18 amFirst weighing: compare groups A and B.
Second weighing: compare groups B and C.
Chris:
Build a balance scale with N trays, such that the trays are positioned as representative of the vertices of a regular polygon with N sides.
For all N=2k+1, place a coin in each tray. The fake coin sits in the only tray, where the two trays opposite of it are level. If the fake coin is at the lowest elevation of all coins, then it is heavier; otherwise it will be at the highest elevation, and thus lighter.
For all N=2k (k!=1), place a coin in each tray. The fake coin is either the coin highest in elevation or lowest. Switch the coin lowest in elevation with one of the two coins beside the one highest in elevation. If the scale does not shift in orientation, the coin highest is the fake (and lighter than the others). If the scale does shift, then the coin lowest is fake (and heavier).
Does not work for N=[0,2]. May require instrumentation more precise than the human eye.
15 April 2010, 9:24 amTanya Khovanova’s Math Blog » Blog Archive » Heavier or Lighter:
[…] my old essay I presented the following coin problem. We have N coins that look identical, but we know that […]
12 November 2010, 11:56 amAlkis Piskas:
Hi everyone!
Since I have not seen a clear cut and complete solution to this coin-weighing problem and since I liked it a lot, here is my contribution (quite late, but good things are durable!)
It can be done for all N>2 and there are more than one methods, depending on N. Here, I tried to forulate a general strategy, that I believe it’s optimum for k-redeem (if I undestood it well):
Divide N by 2. You get 3 parts: P1,P2 containing N1 coins, equal to the quotient, and P3 containing 0/1 coins, equal to the reminder.
1) N2=0 and N1 is even: Weigh P1,P2 against each other. Divide the part that is heavier (say P1) into 2 parts and weigh them against each other: 1a) If they balance (i.e all coins in P1 are good), P2 contains a *lighter* coin. 1b) If they don’t balance, P1 contains a *heavier* coin.
2) N2=0 and N1 is odd: Remove 1 coin from both P1 and P2, setting N1 to even and creating P3 with N2=2. Weigh P1,P2: 2a) If they balance, P3 contains the fake coin. Weigh two coins from P1 (good) against P3. If P1 is heavier, P3 contains a *lighter* coin, otherwise P3 contains a *heavier* coin. 2b) If they don’t balance, proceed as in (1) (ignoring N2).
3) N2=1 and N1 is even: Proceed as in (2) w/o having to remove coins from P1,P2.
4) N2=1 and N1 is odd: Proceed as in (2), with P3 containing now N2=3 coins.
Voila! I hope you enjoyed it!
Alkis
20 November 2013, 2:39 amAlkis Piskas:
Sorry, I just saw that this leaves out N=3 (case (4), which actually was that with which I started my first weighing in the first place!
Well, it is implied that since you can’t remove 1 coin prom either P1 or P2 in (2), you simply weigh P1,P2!
If however we want bloody N=3 included to the general strategu, here is an alternative for case (4):
Proceed as in (2) w/o removing coins from P1,P2. If P1,P2 don’t balance, add the coin from P3 to P1 (which can then be devided exactly), and proceed.
Alkis
20 November 2013, 3:05 amTanya Khovanova:
Alkis, good. Finally we have the answer.
20 November 2013, 9:34 am