Thursday 3 September 2015

A Penny For Your Thoughts, A Scale For Your Counterfeit Penny



Somewhere around 600 BC in the Greek city of Lydia the production of coins began. Usually they used a mixture of precious metals and some base metal. I imagine the first coin was barely in circulation when some guys plotting in the corner of a bath house figured out you could shave a little off the sides and nobody would notice. Thus began the process of counterfeiting coins, and the creation of the term "chiseler." It was a problem that seemed to never find a solution, and finding the fakes, and the chiselers became an ongoing problem. Fast forward to the end of the 17th Century, and one of England's great minds, Sir Isaac Newton, is the director of the mint. It was probably intended to be a token source of revenue for the great mind, but he took it seriously, and one of the famous counterfeiters of all time, William Chaloner, was taken down by the master mathematician/detective.I have heard, but can not confirm, that it was Newton that initiated the idea of milling (putting little ridges or writing) on the edges of coins.

One of the amazing things about recreational mathematics is that the pleasures and pains of daily activity find their way into mathematical problems. Counting activities go back to ancient Papyri, such as the "Going to Saint Ives problem." Games like Tic Tac Toe (noughts and crosses) and mils (Nine Men's Morris) may date back to nearly as early.
River Crossing Problems began as early as the ninth century in a problem book by Alcuin of York, an English scholar, ecclesiastic, poet and teacher from York, Northumbria. Other simple problems seem to spring from clever minds and you wonder how no one ever thought of them before. Eduard Lucas created the simple children's game dots and boxes in the late 19th century. He also created the famous Towers of Hanoi problem.
And counterfeit coins, well it seems they didn't show up until 1945, which surprised me.

I encountered this piece of mathematical history trivia in a paper by Nicholas Diaco and Tanya Khovanova in which they introduced an interesting new variation of the problem genera I will explain later, but first, the history.

It seems that the first counterfeit coin and balance problem appeared in the January 1945  issue of The Mathematical Monthly.   An E. D. Schell submitted the problem, but I do not yet know any detail about him (and of course, if you do, please respond.)  The problem said, "You have eight similar coins and a beam balance. At most one coin is counterfeit and hence underweight. How can you detect whether there is an underweight coin, and if so, which one, using the balance only twice." *Counterfeit Coin Problems, Bennet Manvel, Mathematics Magazine, Vol. 50, No. 2 (Mar., 1977).

 The problem type became immediately popular, with variations sprouting up in every corner.   One such variation asked for the number of weighings necessary if there was one possible counterfeit but it might be either overweight or underweight. The earliest example of this type of problem I have found involved 12 coins, and was submitted by Howard Grossman and appeared in the December 1945 Scripta Mathematica   (I omit to answer these as there are at least 100 places on the internet with solutions.)

The problem submitted by Schell had nine coins, so it seems reasonable to ask, why nine, and what happens if you choose eight, or ten, or 100?    For the mathematical thinker, of course, there was a function hiding in these problems, waiting to be found.

Now there is a variation of these problems that is not listed here, and which I had never seen, nor thought about until today.  What prompted my thoughts was a neat addition to balance problems in the paper mentioned above.  It comes in two variations that seem to have developed over time, so I will give them one at a time, and a site to find solutions.

Version one:
We have 100 coins. Both Cecil and Lisa know the fact that “there are either 1 or 2 counterfeit coins.” Counterfeit coins have the same weight and are lighter than real coins. Given that Lisa knows that there are actually 2 counterfeit coins instead of 1 (and knows exactly which coins they are), find a way for Lisa to prove this fact to Cecil, aided with just a balance, such that at the end of the proof Cecil now knows there are 2 counterfeit coins but does not know the identity of any particular coin.


Version two:
This time, both Cecil and Lisa know the fact “there are 2 or 3 counterfeit coins.” Find a way for Lisa to prove to Cecil that there are actually 3 counterfeit coins, subject to the same conditions as above.


Both versions come from, and are explained at a blog site called Concrete Nonsense .  Variations of them with a different numbers of coins can be found at ARXIV where the paper by  Diaco and Tanya Khovanova  mentioned above.

Now if you've digest all that, you might want to consider this.  Nothing in the problem told you how to find the one, two, or three fake coins.
So consider this a challenge  and I'll look for some really clever solutions from you.  Assume there are a dozen coins, and it is known that there is either one or two fake coins.
Case A (one or both light)
Case B (one or both may be either heavy or light)

How do you find the fake coins?
How many times must the scales be used to find them?

I thought this up while outside painting a building today, and outlining this post in wide brush strokes, so I freely admit I do not know if the questions are solvable, or what the solutions might be.




No comments: