Aside from it posing an extremely interesting and technically challenging problem, this puzzle provides the lecturer with a highly effective educational aid.
It has been in my bag of tricks for many years, providing an excellent platform for explaining and illustrating the difference between formulating a problem and solving a problem. It has also proved a particularly apt tool for expounding the difference between the various paradigms used in decision-making under uncertainty (eg Laplace's Principle of Insufficient Reason vs Wald's Minimax paradigm ).
The puzzle has many versions, some are more difficult than others. In my teaching I use the simple version, namely the case with only one counterfeit coin, and where it is known in advance whether the counterfeit is heavier or lighter than the genuine coins.
It is interesting to note that the official literature on this puzzle focuses on how the puzzle is treated in terms of the worst-case (minimax) paradigm. Thus, the puzzle enables illustrating how, by taking the miminax approach, one eliminates the uncertainty from the problem formulation altogether.
The more elaborate paradigm, where the objective is to minimize the expected number of weighings, proves particularly suitable for illustrating the dynamic programming (DP) solution strategy for sequential decision-making under uncertainty.
I discuss these issues in an online paper, where these two versions of the problem are studied from a DP perspective.
As it turns out the results yielded by the Laplace version of the puzzle are, seemingly, counter-intuitive: the expected number of trials is not monotonic with the size of the problem!!! For example, more weighings — on average — are required to solve a problem of size 6 than a problem of size 7.
I strongly recommend this paper to lecturers who teach topics in decision-making under uncertainty.
Just in case you are not familiar with this puzzle, here is a concise description of it:
You are given a collection of n coins where all but one have the same weight. It is known that the odd (counterfeit) coin is heavier than the other coins.
You are also given a scale with which to determine whether or not any two collections of coins are equal in weight, and if not, which collection is the heavier.
Note that this scale cannot measure the weights of the two collections. It can only determine which of the two collections is the heavier, if at all.
Your task is to work out a weighing scheme that will identify the false coin in as few weighings as possible.
There are, of course, many other versions.
One of the most popular versions is the "Odd 12 Coins Problem" where it is not known in advance whether the false coin is heavier or lighter than the good coins. This problem can be solved in no more than 3 weighings.
More generally, algorithms developed for this type of problems require at most n weighings to solve the puzzle for x = (3n - 3)/2 coins. The "Odd 12 Coins Problem" corresponds to n=3.
The traditional "Computer Science" descriptions of such algorithms involve messy labeling procedures and/or matrix representations. See for example the discussion in WIKIPEDIA.
I much prefer the elegant label-free descriptions proposed by Jack Wert. See
Disclaimer: This page, its contents and style, are the responsibility of the author (Moshe Sniedovich) and do not represent the views, policies or opinions of the organizations he is associated/affiliated with.
You are given a collection of n coins where all but one have the same weight. It is known that the odd (counterfeit) coin is heavier than the other coins.