Sniedovich -- OR/MS Games: 3. Counterfeit Coin Problem.

		Volume 3, Number 2 January, 2003 Table of Contents

OR/MS Games: 3. Counterfeit Coin Problem


Moshe Sniedovich Department of Mathematics and Statistics The University of Melbourne Parkville, VIC 3052, Australia

m.sniedovich@ms.unimelb.edu.au

Abstract

In this discussion we examine two versions of the famous Counterfeit Coin Problem, focusing on their educational OR/MS content. It is shown that this problem provides an excellent environment for illustrating a number of fundamental OR/MS problem-solving concepts and methods related to decision making under uncertainty. A number of interactive modules are provided for experimentation with this problem.

1. Introduction

The Counterfeit Coin Problem is a classical puzzle. It has a long history of challenging ' ... one's reasoning power and ingenuity ...'. It has to do with the following basic situation: There are N coins that are identical in size, shape, color, smell, and general appearance. One coin, however, is counterfeit, having a slightly different weight than the other N-1 coins. The mission is to identify the counterfeit coin - with the aid of a two-pan balance - deploying the smallest possible number of weighings.

Details concerning this standard version of the problem can be found in Albers (1966) and Martelli and Gannon (1997). In our discussion we shall consider the simpler version where the counterfeit coin is known to weight less than the good coins. Hence, formally our problem is as follows:

There are N coins that are identical in size, shape, color, smell, and general appearance. One coin, however, is counterfeit, having a slightly smaller weight than the other N-1 coins. The mission is to identify the counterfeit coin - with the aid of a two-pan balance - deploying the smallest possible number of weighings.

The first fact to notice regarding this problem is that strictly speaking it is not well defined. This fact often puzzles students when they encounter the problem for the first time. It will therefore be constructive to explain why the problem as stated above is not well defined.

Consider the following set-up, describing a situation where there are N = 20 coins and 6 coins are placed in each pan, so there are 20 - ( 2 * 6) = 8 coins off-scale.

The two gold bars are very important in this picture: they are used to support the scale so that the picture depicts a situation where it is not known yet where the counterfeit coin is located.

If we now remove the supporting gold bars, there could be three possible outcomes:

The right pan will rise
The left pan will rise
The scale will remain balanced

Since the same number of coins (6) is placed in each pan, from the decision making perspective the first two outcomes are equivalent: in each case 6 coins will be left for further inspection. On the other hand, the third outcome will leave 8 coins for further inspection. More generally, we distinguish between two cases:

The counterfeit coin is on the scale
The counterfeit coin is off the scale

In the first case 6 coins are left for inspection, in the second case 8 coins will be left for inspection.

What emerges is that there is an inherent uncertainty in the results generated by the weighing process and therefore the problem is ill-defined unless we agree on the rules according to which the outcome of the weighing process is determined.

We shall consider two popular decision-analysis approaches for dealing with this kind of uncertainty, namely

Worst Case Scenario: Mother Nature is playing against us
Laplace's Scenario: each coin is equally likely to be the counterfeit coin

For each case we shall derive an optimal weighing policy.

2. Worst Case Scenario

This is the popular "minimax" approach. It assumes that the worst case will materialize and this way the uncertainty is completely removed. In the context of the counterfeit coin problem under consideration this means that if n coins are left for inspection and x coins are placed in each pan, then exactly

(1)

m = max{x,n-2x}

coins will be left for inspection after this weighing. Thus, in the case depicted in Figure 1, exactly max{6,8} = 8 coins will be left for inspection after the weighing.

Now, let f(n) be the minimum number of weighings required for the identification of the counterfeit coin under the Worst Case scenario given that n coins are left for inspection. Then, it follows - using standard dynamic programming arguments (Sniedovich, 1992) - that

(2)

f(n) = 1 + min {f(max{x,n-2x} : x = 1,2,...,Integer(n/2)})}, n = 2,3,...

with f(1) = 0, where Integer(a) denotes the integer part of number a.

Observe that it is not too difficult to show that f(n) is non-decreasing with n, hence from (2) it follows that

(3)

f(n) = 1 + f(min {max{x,n-2x} : x = 1,2,...,Integer(n/2)}) , n = 2,3,4,...

This means that the optimal value of x can be obtain by solving the following simple problem:

(4)

x(n) = min {max{x,n-2x} : x = 1,2,...,Integer(n/2)}} , n=2,3,...

where clearly x(2) =1.

The notation 'x(n)' is a reminder that the optimal value of x depends on the number of coins left for inspection (n).

Applying the beloved Pigeon Hole Principle (see Burton, 1997) we conclude that the optimal value of x is Integer(n/3), or more specifically:

Recipe for the Worst Case Scenario

If n > 1 coins are left for inspection, place x(n) coins in each pan, where x(n) is the integer computed as follows: Let k and b be the unique non-negative integers such that n=3k + b, b < 3. Then set x(n) = k if b < 2, otherwise set x(n) = k+1.

For example, if n = 12, then k = 4 and b = 0, hence x(12) = 4. If n = 13, then k = 4 and b = 1, hence x(13) = 4 .If n = 14, then k = 4, and b = 2, hence x(12) = 5.

A rough formal proof that this recipe provides an optimal policy goes like this: disregarding the integrality constraint on x, the expression z(n,x) = max{x, n-2x} attains it minimum at a point where x = n-2x. This is so because as x increases n-2x decreases, hence the minimum (over x) of max{x, n-2x} is attained when the line y = x intersects the line y = n-2x. This is illustrated graphically as below.

Explanation *

    Step 1: Draw the x - y plane.

    Step 2: Draw the y = x line.

    Step 3: Draw the y = n-2x line.

    Step 4: Draw the z(n,x) = max{x, n-2x} function.

    Step 5: Locate min {max {x, n-2x}: 0<= x <= 1}.

    Step 6: Solve x = n-2x to obtain y *= x* = n/3.

* Click the radio buttons for a step-by-step construction of the optimal solution.

More formally, let z*(n) = min{z(n,x) = max{x, n-2x}:x in D(n)}. If n = 3k then clearly z*(n) = z(n,k) = k and thus x(n) = k. If n = 3k+1, then clearly z*(n) = z(n,k) = k+1 and thus x(n) = k. If n = 3k+2, then clearly z*(n) = z(n,k+1) = k+1 and thus x(n) = k+1.

One of the characteristics of this problem is that it has many optimal solutions. The following table contains solution obtain by solving the functional equation of dynamic programming for n = 1,...,30. The X(n) column provides the set of all the optimal decisions for the respective value of n.

Table 1

n	f(n)	X(n)
1	0	{}
2	1	{1}
3	1	{1}
4	2	{1,2}
5	2	{1,2}
6	2	{2,3}
7	2	{2,3}
8	2	{3}
9	2	{3}
10	3	{1,...,5}
11	3	{1,...,5}
12	3	{2,...,6}
13	3	{2,...,6}
14	3	{3,...,7}
15	3	{3,...,7}

n	f(n)	X(n)
16	3	{4,...,8}
17	3	{4,...,8}
18	3	{5,...,9}
19	3	{5,...,9}
20	3	{6,...,9}
21	3	{6,...,9}
22	3	{7,8,9}
23	3	{7,8,9}
24	3	{8,9}
25	3	{8,9}
26	3	{9}
27	3	{9}
28	4	{1,...,14}
29	4	{1,...,14}
30	4	{2,...,15}

The following module can be used to generate the f(n) and X(n) values for larger values of n.

	WORST CASE Scenario
	Total number of coins: N = (range 1-500)
Status :

The following is then the basic result regarding the relationship between n and f(n).

Theorem 1
f(n) is non-decreasing with n and is equal to the smaller integer value m such that 3^m >= n, that is f(n) = Ceiling(log₃(n)), where Ceiling(a) is the smallest integer m such that a <= m.

It is left as an optional exercise for the interested reader to quantify the relationship between x and X(n). Here are some examples:

Theorem 2
If k > p are elements of X(n) then any m such that k > m > p is also an element of X(n).

Theorem 3
If n = 3^k or n = 3^k-1, where k is a positive integer, then X(n) = {n/3}, namely for such values of n there is a unique optimal decision.

Theorem 4
If n = 3^k+1, where k is a positive integer, then X(n) = {1,...,Integer(n / 2)}, namely for such an n all the feasible decisions are optimal.

Theorem 5
If n is such that 3^k > n > 3^k+1, then X(n) is bounded above by 3^k.

These results indicate that X(n) is well behaved. In particular, the size (cardinality) of X(n) is increasing sharply at values of n such that n = 3^k+1, and then X(n) is contracting as n increases, until n = 3^k+1-1 where it becomes a singleton, {3^k}. This pattern is repeated in the interval {3^k+1,3^k+2}, and so on.

Exercise: Find a closed-form expression for the smallest and largest elements of X(n), hence X(n) itself.

One of the important implications of these features of X(n) is that the number of optimal solutions is pretty large for n that is not close to a power of 3.

3. Laplace's Scenario

Assume that each coin is equally likely to be the counterfeit coin and let P[on|n,x] be the probability that the false coin is on the scale given that m coins are to be inspected and x coins are placed in each pan. Similarly, let P[on|n,x] be the probability that the false coin is off the scale given that m coins are inspected and x coins are placed in each pan, so that P[on|n,x] = 1-P[off|n,x]. Then it is not too difficult to show that

(5)

P[ 'on' | n,x ] = 2x/n

(6)

P[ 'off' | n,x ] = (n-2x)/n

Now let

F(n) =	Expected value of the total number of weighings required for the identification of the counterfeit coin when an optimal weighing policy is used to solve a problem of size n. Clearly, F(1) = 0, F(2) = F(3) = 1.
F(n\|x) =	The same as above, except that the first decision is to place x coins in each pan, x = 1,2,...,Integer( n / 2).
X(n) =	Set of optimal values of the first decision when n coins are left for inspection, n > 0. Clearly, X(0) = X(1) = {}, X(2) = X(3) = {1}.

Also observe that by definition,

(7)

F(n) = min {F(n|x) : x in D(n)} , n = 2,3,...

where D(n) = {1,2,...,Integer(n/2)}.

It should be stressed that we have to be careful here with regard to what we mean by 'an optimal policy'. In sharp contrast to the Worst Case scenario, here it may be advantageous to 'borrow' a good coin so as to speed up the process. Differently put, here F(n) is not monotonic with n, that is F(n) is not non-decreasing with n. For example, as we shall shortly see, F(6) = 2 > F(7) = 13/7. We shall refer to such a good coin as a reference coin.

For this reason it is convenient to first consider the case where through the weighing process it is not allowed to add a reference coin to the collection of coins left for inspection from the previous trial. We refer to this version of the problem as the 'Simple Laplace's Scenario'.

It is not difficult to show - using standard dynamic programming arguments - that in this case the following functional equation is valid:

(8)

	F(n\|x) =	P[on\|n,x]F(x) + P[off\|n,x]F(n-2x)
	=	(2x/n)F(x) + ((n-2x)/n)F(n-2x)

From (5)-(8) it follows then that:

Theorem 6

(9)

F(n) = 1 + min {(2x/n)F(x) + ((n-2x)/n)F(n-2x): x in D(n)} , n = 2,3,...

Table 1 displays the results obtained by solving this functional equation for n = 1,2, ..., 30. Values of n for which F(n+1) < F(n) are highlighted and marked (*). X'(n) denotes the set of optimal decisions if n coins are left for inspection.

Table 2

n	F(n)	X'(n)
1	0	{}
2	1	{1}
3	1	{1}
4	3/2	{1}
5	8/5	{1}
6	2	{1,2,3}
7	13/7	{3}
8	2	{3}
9	2	{3}
10	11/5	{3}
11	25/11	{3}
12	5/2	{3,4,5}
13	32/13	{3,5}
14	18/7	{3,5}
15	13/5	{3,5}

n	F(n)	X'(n)
16	11/4	{3,4,5,7}
17	46/17	{5,7}
18	25/9	{5,7}
19	53/19	{5,7}
20	29/10	{5,7,8,9}
21	20/7	{7,9}
22	32/11	{7,9}
23	67/23	{7,9}
24	3	{7,8,9}
25	74/25	{9}
26	3	{9}
27	3	{9}
28	43/14	{9}
29	90/29	{9}
30	16/5	{9,10,11}

Fraction / = Decimal

You can use the Fraction-to-Decimal conversion facility at the bottom of Table 2 to verify these facts (fill in the two fraction fields and then click the decimal field).

You might be interested in using the module below to generate values of F(n) for values of n larger than 30.

	Simple Laplace's Scenario
	Total number of coins: N = (range 1-300)
Status :

Exercise: Try to find some patterns in the structure of F(n) and X'(n). In particular, examine the behaviour of the smallest and largest elements of X'(n), hence X(n) itself, as n increases.

Observe that there are many 'anomalies' of the kind discussed above, in fact for large n about one quarter of the F(k) values are such that F(k+1) < F(k).

Experience indicates that most students - and some adults - find this phenomenon somewhat counter intuitive if not puzzling. It might be useful therefore to briefly explain this 'strange' behaviour.

Consider the case where there are n=6 coins for inspection and assume that we place x = 3 coins in each pan. As indicated in Table 2, this is an optimal decision. For this case P[on|6,3] = 1, P[off|6,3] = 0, hence,

F(6) = 1 + 1xF(3) + 0xF(0) = 1 + 1 + 0 = 2

Now suppose that we can borrow a reference coin. Then we can do the following:

Place 3 unchecked coins in one pan
Place 2 unchecked coins and a reference coin in the second pan
Place one unchecked coin off the scale

Figure as below depicts this scheme versus the scheme used to compute F(6|3) in accordance with (8).


n = 6, x = 3 without a reference coin		n = 6, x = 3 with a reference coin

Let F(6|1 ref) denote the expected value of the total number of weighings required to identify the counterfeit coin using one reference coin as explained above, and using the conventional optimal decisions in subsequent weighings.

We thus have,

(10)

	F(6\|1 ref) =	1 + (5/6)x{(3/5)F(3) +(2/5)F(2)} + (1/6)xF(0)
	=	1 + (5/6)x1 + (1/6)x0
	=	11/6 = 1.833333333

In contrast, since x = 3 is an optimal decision for n = 7, we have

(11)

	F(7) =	1 + (6/7)xF(3) + (1/7)xF(1)
	=	1 + (6/7)x1 + (1/7)x0
	=	13/7 = 1.857142871

Observe that, as expected, F(6|1 ref) <= F(7).

Let us now consider the case where in each weighing it is allowed to use one additional reference coin in the manner described above and let

F*(n) =	Expected value of the total number of weighings required for the identification of the counterfeit coin when an optimal weighing policy is used to solve a problem of size n. Clearly, F(1) = 0, F(2) = F(3) = 1.
F*(n\|x,0) =	The same as above, except that the first decision is to place x coins in each pan (not using a reference coin).
F*(n\|x,1) =	The same as above, except that the first decision is to use a reference coin, thus placing x unchecked coins in one pan, (x-1) unchecked coins and the reference coin in the other pan, and n-2x+1 unchecked coins off the scale.
F*(n\|x) =	min {F[n\|x,0] , F[n\|x,1]}.
X*(n) =	Set of optimal values of the first decision when n coins are left for inspection, n > 0. Clearly, X(0) = X(1) = {}, X(2) = X(3) = {1}.

These entails the following:

Theorem 7

(12)

F*(n|x,0) = 1 + (2x/n)F*(x) + ((n-2x)/n)F*(n-2x)

(13)

F*(n|x,1) = 1 + (x/n)F*(x) + ((x-1)/n)F*(x-1) + ((n-2x+1)/n)F*(n-2x+1)

(14)

F*(n) = 1 + min {F*(n|x): x in D(n)} , n = 2,3, ...

Table as below lists the values of F*(n) for n = 1,...,30 and the respective values of X*(n). Instances where F*(n) < F(n) are highlighted. The notation k^ is used to represent decisions utilizing a reference coin. Thus, 5^ represents the decision "place 5 unchecked coins in one pan, 4 unchecked coins and the reference coin in the other pan, and the remaining (n-9) unchecked coins off the scale.

n	F*(n)	X*(n)
1	0	{}
2	1	{1,1^}
3	1	{1}
4	3/2	{1,2^}
5	8/5	{1}
^6^	11/6	{2^,3^}
7	13/7	{3}
8	2	{3,3^}
9	2	{3}
^10^	11/5	{3,4^}
11	25/11	{3}
12	29/12	{3,4^,5^}
13	32/13	{3,5}
14	18/7	{3,4^,5,5^,6^}
15	13/5	{3,5}

n	F*(n)	X*(n)
^16^	43/16	{4^,5,5^,6^,7^}
17	46/17	{5,7}
18	25/9	{5,5^,6^,7,7^,8^}
19	53/19	{5,7}
^20^	57/20	{6^,7,7^,8^,9^}
21	20/7	{7,9}
22	32/11	{7,7^,8^,9,9^}
23	67/23	{7,9}
^24^	71/24	{8^,9,9^}
25	74/25	{9}
26	3	{9,9^}
27	3	{9}
28	43/14	{9,10^}
29	90/29	{9}
^30^	19/6	{9,10^,11^}

Fraction / = Decimal

Certain patterns are revealed so you are encouraged to use the module below to generate values of F*(n) and X*(n) for values of n larger than 30.

	Laplace's Scenario with One Reference Coin
	Total number of coins: N = (range 1-300)
Status :

Decisions marked (^) represent instances where a reference coin is used. For example, 5^ means that 5 unchecked coins are placed in one pan and 4 unchecked coins and the reference coin are placed in the other pan.

There are a number of obvious patterns that deserve attention. For instance,

As expected, F*(n) <= f(n) for all n > 0.
For n = 3^m, X*(n) is a singleton comprising the optimal solution to the Worst Case Scenario given by the recipe introduced in Section 2, namely X*(n) = {n/3}, and therefore F*(n) = f(n) = m.
This minmax recipe does not provide optimal solution for all n. For example, X*(11) = {3} does not include x(11) = 4.
If n is odd then X*(n) consists only of odd integers none of which requires the reference coin.

In view of the role of the reference coin in the analysis of the Laplace's Scenario, it is only natural to ask the question: would it be advantageous to use two (or more) reference coins? The following module can be used to generate optimal solutions for the case where 2 reference coins are allowed.

	Laplace's Scenario with Two Reference Coins
	Total number of coins: N = (range 1-300)
Status :

Decisions marked (*) represent instances where it is optimal to use two reference coins. For example, 5* means that 5 unchecked coins are placed in one pan and 3 unchecked coins and two reference coins are placed in the other pan.

Exercise: Let F**(n) denote the expected value of the number of weighing required by an optimal policy to identify the counterfeit coin in a problem of size n if two reference coins can be used. Show that F**[n] = F*[n] for all n, or find an n such that F**[n] < F*[n]. How about using more than 2 reference coins?

4. Robustness

The following question naturally arises: is there a solution policy, say Y = Y(n), that is optimal for both the Worst Case Scenario and the Laplace's Scenario?

Given that there are so many optimal solutions to the problem under the Worst Case Scenario, it makes sense to investigate whether one of these is also optimal for the Laplace's Scenario. In particular, is the 'divide by 3' policy that is optimal for the Worst Case Scenario is also optimal for the Laplace's Scenario?

The answer is no. For example, for n = 18, under the Simple Laplace's Scenario we have X'(18) = {5,7} so the 'divide by three' solution x = 6 is not optimal here. Similarly, under the Laplace's Scenario with one reference coin, X*(18) = {5,5^,6^,7,7^,8^} so here again the 'divide by three' solution x=6 is not optimal, although its close colleague, namely 6^ is optimal here.

However, as we noted above (Theorem 2 - Theorem 5), under the Worst Case Scenario there are many optimal solutions. This can be even more pronounced if a reference coin can be used. So let X"(n) be the set of optimal decisions for the Worst Case Scenario if n coins are left for inspection and a reference coin can be used. For example, for n=6 we have X(6) = {2,3} and X"(6) = {2,2^,3,3^}. Since X*(6) = {2^,3^}, the elements of the intersection of X"(6) and X*(6), namely {2^,3^}, are optimal with respect to n for both the Worst Case Scenario and the Laplace's Scenario. What then is the structure of X"(n)?

Theorem 8
If d is in X(n) but it is not the smallest element of X(n), then d^ is an element of X"(n).

For example, X(13) = {2,...,6} so X"(13) must contain X(13) as well as the set {3^,...,6^}. Note that it does not contain the decision 2^.

Exercise: Construct a policy d = d(n) that is optimal both for the Worst Case Scenario and the Laplace's Scenario. Hint: any policy d = d(n) such that for every n the decision d(n) is an element of the intersection of X"(n) and X*(n) will do the job.

5. Related Problems

Given the so natural and down to earth nature of the puzzle and the very rich literature about it, one is inclined to regard it as an old treasure. It is surprising therefore that the puzzle first appeared on the scene only in 1945 - as a problem contributed to the American Mathematical Monthly. The full text is as follows:

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?

E.D.Schell (1945)

The computer science and recreational mathematics literature is mainly concerned with the more difficult problem where - under the worst case scenario - it is unknown whether the counterfeit coin is heavier or lighter than the good coins (eg. Linial and Taris, (1982), Hwang, (1987), Bundy, (1996)). The favorite problem size is n = 12, in which case only 3 weighings are necessary (assuming that there is exactly one bad coin in the collection). More generally, the largest problem that can be solved with no more than k weighings is of size n = (3^k-3)/2.

It is interesting to note that puzzles of this type have pre-determined optimal weighing schemes, namely schemes that proceed independent of the results of the weighings. A great deal of effort was made to improve the description and representation of such policies (Manvel, (1977), Martelli and Gannon, (1997)).

There are of course other versions of the puzzle, including cases where there are more than 2 pans (De Bonis, (1998)), problems where there is more than one counterfeit coin (Tosic, (1983)) and problems where the number of counterfeit coins is unknown (Pyber, (1986)).

Bellman and Glass (1961) use DP to solve a variety of counterfeit coin problems. It is interesting that the treatment of the Laplace's Scenario case does not include the option of using a reference coin.

Not surprisingly, this challenging puzzle has strong presence on the WWW: see Yahoo's directory of Math Problems, Puzzles and Games. In particular, it features in the tutOR and tutORial projects.

Needless to say, both conceptually and technically, this problem is strongly related to "practical" problems such as detecting defective members of large populations and group testing.

6. Conclusions

The counterfeit coin problem is an excellent source of OR/MS educational material. It has very simple versions as well as extremely difficult ones. Its analysis involves fundamental concepts in decision making under uncertainty which can be vividly illustrated and experimented with.

It is a pity that this educationally rich puzzle has not yet established itself as a common topic of discussion in introductory OR/MS textbooks.

This article is part of the author's effort (Sniedovich, (2002) to encourage OR/MS lecturers to incorporate OR/MS games and puzzles in their courseware.

References

Albers, D. J. (1996), "Tom Banchoff: Multidimensional Mathematician," Math Horizons, pp. 18-22.

Bellman, R. and Glass, B. (1961), "On Various Versions of the Defective Coin Problem," Information and Control, Vol. 4, pp. 118-131.

Bundy, B.D. (1996), "The Oddball Problem," Mathematical Spectrum, Vol. 26, pp. 14-15.

Burton, D.M. (1997), Elementary Number Theory, McGraw Hill, NY.

De Bonis, A. (1998), "A Predetermined Algorithm for Detecting a Counterfeit Coin with Multi-arms Balances," Discrete Applied Mathematics, Vol. 86, pp. 191-200.

Hwang, F.K., (1987), "A Tale of Two Coins," American Mathematical Monthly, Vol. 94, pp. 121-129.

Linial, N. and Taris, M. (1982), "The Counterfeit Coin Problem Revisited," SIAM Journal on Computing, Vol. 11, No. 3, pp. 409-415.

Manvel, B. (1977), "Counterfeit Coin Problems," Mathematics Magazine, Vol. 50, No. 2, pp. 90-92.

Martelli, M. and Gannon, G. (1997), "Weighing Coins: Divide and Conquer to Detect a Counterfeit," College Mathematics Journal, Vol. 28, pp. 365-367.

Pyber, L. (1986), "How to Find Many Counterfeit Coins?," Graphs and Combinatorics, Vol. 2, pp. 173-177.

Schell, E.D. (1945), E651, American Mathematrical Monthly, p. 42.

Sniedovich, M. (1992), Dynamic Programming, Marcel Dekker, NY.

Sniedovich, M. (2002), "OR/MS Games 1. A Neglected Educational Resource", INFORMS Transactions on Education, Vol. 2, No, 3, http://ite.informs.org/Vol2No3/Sniedovich/.

Tosic, R. (1983), "Two Counterfeit Coins," Discrete Mathematics, Vol. 46, pp. 289-295.

tutOR Project: www.tutor.ms.unimelb.edu.au.

tutORial Project: www.ifors.org/tutorial/.

Yahoo's directory of Math Problems, Puzzles and Games: http://dir.yahoo.com/Science/Mathematics/Problems__Puzzles__and_Games/.

^ã INFORMS

	To download a printable version (pdf) of this paper, click here. To download the Adobe Acrobat reader for viewing and printing pdf files, click here.
	To post a message (or read messages that have been posted) about this document, please go to the ITE message board and select the conference titled ".....Sniedovich -- OR/MS Games: 3. Counterfeit Coin Problem"
	To reference this paper, please use: Sniedovich, M. (2003), "OR/MS Games: 3. Counterfeit Coin Problem." INFORMS Transactions on Education, Vol. 3, No. 2, http://archive.ite.journal.informs.org/Vol3No2/Sniedovich/