Scary Coins
My coauthor Konstantin Knop publishes cute math problems in his blog (in Russian). Recently he posted a coin weighing problem that was given at the 2010 Euler math Olympiad in Russia to eighth graders. The author of the problem is Alexander Shapovalov.
Among 100 coins exactly 4 are fake. All genuine coins weigh the same; all fake coins, too. A fake coin is lighter than a genuine coin. How would we find at least one genuine coin using two weighings on a balance scale?
It is conceivable that your two weighings may find more than one genuine coin. The more difficult question that Konstantin and his commentators discuss is the maximum number of genuine coins you can guarantee to identify in two weighings. Konstantin and the others propose 14 as the answer, but do not have a proof yet.
I wonder if one of you can find a bigger number than Konstantin or alternatively a proof that indeed 14 is the largest possible.
You might ask, considering the title of this piece, why I think that coins are scary. No, I am not afraid of coins. It scares me that this problem was given to eighth graders in Russia, because I cannot imagine that it would be given to kids that age in the USA.
By the way, ten eighth grade students in Russia solved this problem during the competition.
Share:
Xamuel:
The problem is slightly ambiguous.
Do you mean:
“What’s the biggest number N such that some selection-of-coins-to-weigh and result-of-weighing-them allows you to identify N genuine coins, *regardless* of how much real coins and fake coins weigh?”
Or:
“What’s the biggest number N such that some selection-of-coins-to-weigh and result-of-weighing-them and some weight-of-fake and some weight-of-genuine-coins, allows you to identify N genuine coins?”
Or:
“What’s the biggest number N such that there is some strategy which will always let you identify N genuine coins, regardless of how much real coins and fake coins weigh?”
Or:
“What’s the biggest number N such that, for any given weight-of-real-coins and a given weight-of-fake-coins, there exists a corresponding strategy which will always let you identify N genuine coins?”
I’m guessing it’s the first one, but I wanna be sure… 🙂
16 June 2010, 3:11 pmTanya Khovanova:
I mean:
What is the biggest number N such that regardless of the results of each individual weighing, your strategy will allow you to identify at least N genuine coins?
16 June 2010, 3:55 pmMaynard Handley:
“It scares me that this problem was given to eighth graders in Russia, because I cannot imagine that it would be given to kids that age in the USA.”
This seems like a remarkably silly statement. You state yourself that the question was given at “the 2010 Euler math Olympiad in Russia to eighth graders.”, ie not to the run of the mill Russian students.
Certainly the US has comported itself extremely well at the International Math Olympiad, and there seems no reason to imagine that that reservoir of talent somehow matures only after 8th grade, following a different pattern from Russia.
Why does this matter? Because a constant stupidity running throughout discourse about education in the US is an inability (or unwillingness) to distinguish between the median behavior of the system and its behavior at the high end. Most recently we saw this in the nonsense surrounding Larry Summers’ statements where his point, valid or not, had to do with the rightmost extreme of the graph of mathematically talented individuals, yet most of his critics went on and on about the behavior of the mean of this distribution, apparently unaware of the foolishness of their arguments.
The US may do a great job of educating its best students. It may do a lousy job compared to what is possible. Who knows? One thing that is clear, however, is that facile references to the known shortcomings of the US system when it comes to the median student do NOTHING to help us learn about this issue.
17 June 2010, 12:12 amKonstantin Knop:
https://docs.google.com/fileview?id=0ByXEl13981ctMmVlMzkxODgtOGQ1My00ZTJjLThkZTItNDgxNGY2MjllYjk5&hl=ru
17 June 2010, 3:46 am(sorry, it’s Russian text)
Tanya Khovanova:
Maynard,
Math education in US scares me. If we were better educated, Americans wouldn’t have bought subrpime mortgages and so on. Many financial and other big mistakes could have been avoided.
Also, our relatively good success in IMO is due to immigrants. Research shows that a very small portion of the Amerian IMO team are not immigrants, and those are mostly home-schooled.
17 June 2010, 9:36 amcolorblind:
“If we were better educated, Americans wouldn’t have bought subprime mortgages”
The mortgages were sold with the buyers having the belief that 1) the market wouldn’t collapse, 2) Interest rates wouldn’t increase, and 3) their personal income would improve. Without the benefit of hindsight, those are not horrible assumptions. Of course – and this is both the virtue and the vice of Americans (IMHO) – nobody bothered to hedge for the “unlikely” possibility something would go wrong.
With that in mind, I think “more education” is a red herring. There were educated people who understood the mortgages who could have used their knowledge, but they chose not to, in many cases because they wanted the largest personal gain and, here it comes again, did not hedge for the “unlikely” possibility something would go wrong.
I would certainly argue Americans have some innumeracy with regard to risk, but that it seems to be a matter of temperament rather than education.
(BTW, I really am working on the problem…the assumption being if there is a 15 coin solution, then it constitues a 14 coin solution. The known 14 coin solution is based on the solution to the original problem (I think…I’m trying to do this within down time that’s a function of seconds) and that does not extend to a 15 coin solution. Therefore, a 15 coin solution exists if and only if the known 14 coin solution is not unique. Luckily, the number of first and second weighings is finite and a large swath of first weighings possibilities can be eliminated easily, so a uniqueness proof seems doable.)
17 June 2010, 9:51 pmSpiked Math:
If you really want something to think about, consider a generalization of the problem:
Let “k” and “f” be given natural numbers with “f=3”?
Of course, above “N” depends on the choice of “k,f,w”, so is a function. Find the function.
18 June 2010, 4:53 amSpiked Math:
(Sorry Tanya, I didn’t use the right code for less than and greater than signs before):
If you really want something to think about, consider a generalization of the problem:
Let “k” and “f” be given natural numbers with “f<=k”. Among “k” coins exactly “f” are fake. All genuine coins weigh the same; all fake coins, too. A fake coin is lighter than a genuine coin. For what values of “k” and “f” can we find at least one genuine coin using two weighings on a balance scale? How would you do it?
What is the biggest number “N” such that regardless of the results of each individual weighing, your strategy will allow you to identify at least “N” genuine coins?
What if we allow “w” weighings for some integer “w>=3”?
Of course, above “N” depends on the choice of “k,f,w”, so is a function. Find the function.
18 June 2010, 4:56 amcolorblind:
update: yeah! (with initial caveat) Unfortunately, the generalization of the first problem I thought I had earlier only leads to a 13 coin solution. 29 coins for each side on the first weighing. If unequal, split the group with less fake coins to find at least 14 real coins. If equal, put the 42 unmeasured on one side and one of the first two piles along with 13 coins from the other of the first two piles. The “trick” to get to 14 is to add one of the unused coins to each pile on the second weighing. From what I can make of Konstantin’s link, that’s his 14 solution also.
For the proof of “no 15” hypothesis, I think a few things are to be proved:
1) All weighings must compare equal quantities of coins (Obvious, but even/odd will come into play later.)
2) Not all coins can be weighed on the first weighing (Kind of obvious, but allows us to partition the 100 coins into three groups for the first weighing, which is critical for the second weighing.)
3) If the first weighing results in equality, then all coins must be weighed at some point. (Not entirely obvious, but this forces any suitable algorithm to be very similar to the 13 coin solution mentioned above.)
4) If the first weighing results in equality, the unweighed coins from the first part must be in the same group when weighed during the second part. (A little work here, but no hard lifting.)
5) If the first weighing results in equality, the unweighed coins cannot be exactly one of the groups on the second weighing. (If that is so, the max coins that can be found is 13, from the generalization of the solution to the initial problem)
6) If the first weighing results in equality, adding 2 or more coins from one of the first two piles to the unweighed pile to create a group for the second weighing will result in no solution due to ambiguities.
Once those 6 points have been proved, we have what we need to finish both a uniqueness proof for the 14 solution and a “no 15” proof as desired. My main concern is 3). Intuitively, it makes sense; any unweighed coins will result in significantly less information destroying a possible solution. Thoughts?
18 June 2010, 8:16 pmSamanta:
I can’t figure out a solution to this one. Any hint on how to solve this even for just one normal coin. By splitting into 33, 33, 33 & 1 we can find a normal coin in two weighings but one corner case, i.e. when there is an odd coin in each of these 4 groups, kills me. If I split into 5 groups of 20 each and can somehow find the heaviest group in two weighings then that will give the solution but to find the max among 5 means again 3 weighings.
23 June 2010, 6:59 pmJean Drabbe:
Hi Tanya,
31 July 2010, 3:45 amIn the first message of this thread you cite Knop’s paper on Shapovalov coin problem (in Russian).
Does it go any further than the algorithm described above by Colorblind ?
If so, could you please write a short abstract/review stating the main result ?
That would be helpful for people like me who don’t understand Russian.
Thank you.
Jean Drabbe (Belgium)
Giovanni Ciriani:
I found this blog recently, and I’m still working on this problem. However, I started from a lower-number-of-coins scenario, to find a scalable algorithm with which to crack the statement problem. Based on that I’m inclined to think that there is a better solution than 14. With 2 balls for instance, I found out that with 2 weighings one can find out at least 16 balls out of a pool of 25 balls of which 2 are lighter.
15 October 2010, 2:23 pm8th Grade Math Games:
Wow that’s an incredibly hard question for 8th grade. But I do think American 8th graders could still do it though. Lets see though, anyone reading this teach the 8th grade? If you do see if your class can do this question than come back here and let us know.
22 October 2010, 8:37 amDima Q:
My guess is 20 genuine coins is max.
Following efimp’s solution in comments to knop’s blog:
split all coins to A,B,C; A=B in count; if A>B in weight, take x=y from A, if x>=y in wieght, x are geniune;
if A=B in weight, take x from A, (B+x)=C in count; (B+x)>C -> x genuine; (B+x)=C -> A-x genuine; (B+x) C genuine;
genuine outcomes are: x,y,A-x,C; constraints are x=y, 2x<=A, A=B, 100=C+A+B; this is simplified to maximization of x and 100-4x; thus x=100/5=20;
This of course only shows that 20 is possible; it’s not a proof that more is impossible.
26 January 2011, 6:36 pmByron:
Dima, this is good, but I think you missed a couple things. If 20 is possible, then let’s substitute back. So, x>=20, y>=20, A-x>=20, C>=20. Therefore, A>=40, B>=40, and C<=20. Therefore, the B+x=C uses a negative x.
One missing constraint is A<C. In other words, 2x<100-4x, or x<16.67
Another missing constraint is B+x=C. In other words, 2x+x<100-4x, or x<14.29
So, given this strategy, it seems that 14 is optimal.
23 April 2011, 10:11 am