Label the coins with the letters A,C,D,E,F,I,K,L,M,N,O,T and then weigh

- them as follows
- MADO vs. LIKE METO vs. FIND FAKE vs. COIN

You don't need to memorize the letter list, just the phrase "Ma do like me to find fake coin." Alternatively, you can use the phrase "MIND LOCK FEAT" or "FAKE MIND CLOT" or "MIT FOLK DANCE."

The following table of outcomes tells you which coin is heavy or

- light ("L" = left down, "R" = right down, "=" = balance)
- LLL I light
LL= M heavy
LLR O heavy
L=L A heavy
L== L light
L=R K light
LRL
LR= D heavy
LRR E light
`LL N light`M light RRR I heavy`L`T heavy`LR F light ==L C light === ==R C heavy`D light RLR R=L K heavy R== L heavy R=R A light RRL O light RR`RL F heavy =R`T light =RR N heavy RLL E heavy RL

Here are some other mnemnonic labelings:

Label the coins with letters from the phrase "THE KP FORMULA" and weigh

- them according to these words
- TAKE vs. FOUR PARK vs. THEM HALF vs. MORE

Another solution can be found by switching the labels F and U. This

- gives
- TAKE vs. FOUR PARK vs. THEM HAUL vs. MORE

Another solution uses the phrase "MAUDLIN POWER" and weigh them

- according to these words
- PLOW vs. IDEA DIAL vs. RUNE RIPE vs. MOAN

Another solution uses the phrase "HARVEST LOGIC" and weigh them

- according to these words
- ISLE vs. CHAT GAVE vs. TOIL HAIR vs. COVE

The general solution with N coins can be solved using the following algorithm. A program that prints out the explicit weighings and how to interpret the results is listed at the end of this article.

Assume that you are allowed W weighings. Write down the 3^W possible length W strings of the symbols '0', '1', and '2'. Eliminate the three such strings that consist of only one symbol repeated W times.

For each string, find the first symbol that is different from the symbol preceeding it. Consider that pair of symbols. If that pair is not 01, 12, or 20, cross out that string. In other words, we only allow strings of the forms 0*01.*, 1*12.*, or 2*20.* ( using ed(1) regular expressions ).

You will have (3^W-3)/2 strings left. This is how many coins you can handle in W weighings.

- Perform W weighings as follows
For weighing I, take all the coins that have a 0 in string position I, and weigh them against all the coins that have a 2 in string position I.

If the side with the 0's in position I goes down, write down a 0. If the other side goes down, write down a 2. Otherwise, write down a 1.

After the W weighings, you have written down an W symbol string. If your string matches the string on one of the coins, then that is the odd coin, and it is heavy. If none of them match, than change every 2 to a 0 in your string, and every 0 to a 2. You will then have a string that matches one of the coins, and that coin is lighter than the others.

Note that if you only have to identify the odd coin, but don't have to determine if it is heavy or light, you can handle one more coin, or up to (3^W-1)/2 coins. Label the extra coin with a string of all 1's, and use the above method. This coin will never be weighed, but if all the weighings result in balances, you know that this coin is the counterfeit, although you do not know whether it is heavier or lighter.

Note also that you can handle one more coin, or up to (3^W-1)/2 coins,
if you **do** have to determine whether it is heavy or light, provided
that you have a reference coin, which you know has the correct weight.
You do this by labeling the one extra coin with a string of all 2s.
This results in it being placed on the same side of the scales each
time, and in that side of the scales having one more coin than the
other each time. Put the reference coin on the other side of the
scales to the "all 2s" coin on each weighing.

Proving that this works is straightforward, once you notice that the method of string construction makes sure that in each position, 1/3 of the strings have 0, 1/3 have 1, and 1/3 have 2, and that if a string occurs, then the string obtained by replacing each 0 with a 2 and each 2 with a 0 does not occur.

Proving that this is the optimal solution (i.e., the solution that uses the least number of weighings) can be done as follows.

There are 3^W different possibilities in W weighings on the scale (i.e., left pan goes down, right pan goes down, or the pans balance). If the counterfeit coin appears in any of these weighings, one side of the scale will go down, but you cannot tell whether a heavy coin was on that side or a light coin on the other side, so identifying the counterfeit uses at least two cases. If it does not appear in any of the weighings, identifying it uses up only one case, but this can only be done for one coin. Thus you can theoretically identify the counterfeit coin among (3^W+1)/2 coins, which is 14 coins for three weighings.

However, you cannot do this unless you have one coin which is guaranteed to be genuine. The reason is that the first weighing must test two groups of equal sizes. If both groups are of size (3^(W-1)-1)/2 or smaller and the first weighing balances, you will be left with at least (3^(W-1)+3)/2 unweighed coins, which cannot be handled in the remaining W-1 weighings. If both groups are of size (3^(W-1)+1)/2 or larger and the first weighing doesn't balance, you now have at least 3^(W-1)+1 cases left and you have already weighed the bad coin, so you cannot handle this in W-1 weighings.

The solution shows how to weigh (3^W+1)/2 coins given one genuine coin (this allows you to weigh (3^(W-1)+1)/2 unknown coins against (3^(W-1)-1)/2 unknown coins plus the genuine coin in the first weighing), and how to weight (3^W-1)/2 coins without a genuine coin to use. In each case, the coin with number all 1's is not weighed, so if the scales balance three times, you know that this is the bad coin but not whether it is heavy or light. Therefore, if you must identify whether the counterfeit is heavier or lighter, you must exclude the all 1's coin, and the most you can handle is (3^W-3)/2.

If you already know the odd coin is heavy (or light), you can handle 3^W coins. The algorithm in this case:

Divide the coins into three equal groups... A, B, and C. Weigh A against B. If a pan sinks, it contains the heavy coin, otherwise, the heavy coin is in group C. If your group size is 1, you've found the coin, otherwise recurse on the group containing the heavy coin.

To solve the 12 coin problem if 1 "lie" is allowed:

Six weighings are required. Label the weighings "abcdef;" "abc" and "def" each are in the same pattern as the non-lie 12 coins problem.

primary code inverted code 001 200 221 022 220 011 002 211 010 002 212 220 011 010 211 212 012 021 210 201 202 110 020 112 201 102 021 120 200 121 022 101 122 202 100 020 121 221 101 001 120 210 102 012 112 122 110 100

They are related by the following equations

d=(a+b-1) mod 3 e=(b+c-1) mod 3 f=(c+a-1) mod 3

After the weighings, see which equations fail

"lie"

none none

f f

e e ef c

d d d f a d e b def impossible

If the "lie" is A, B, or C, use the results of D, E, and F to determine which coin weighs different, and whether it is heavy or light. Similarly, use ABC if the "lie" is among DEF.

5 weighings is not enough, because that can only give a total of 243 results. 5 weighings give 2 * 12 coin possibilities and 11 lie possibilities (2 incorrect on each weighing, and 1 where there is no lie) for a total of 264 total possibilities.

Many more cases are covered in the literature. For a summary of known

- and unknown results and a bibliography, see
- Coin-Weighing Problems Richard K. Guy and Richard J. Nowakowski The American Mathematical Monthly Volume 102 Number 2 / February 1995 p. 164

Older references:

Counterfeit Coin Problems. Manvel, Bennet. *Mathematics Magazine*
50 (1977) 90-92.

A Combinatory Detection Problem. Soderberg and Shapiro. *The
American Mathematical Monthly* 70 (1963) 1066.

Remarks on Detection Problems. Frank and Silverman. *The
American Mathematical Monthly* 74 (1967) 171.

Diophantine Problems in Weighing. Simmons. *The American
Mathematical Monthly* 34 (1927) 4.

On a Chainomatic Analytical Balance. Klamkin. *The American
Mathematical Monthly* 62 (1955) 188.

--------------------------- cut here ----------------------------------

/* Inspired by the posting below from James Campbell, this is a quick little C program to print particular solutions to the generalized "12 coins" problem. Run the program, give it a command-line argument of the number of WEIGHINGS you want to do, and it will tell you how to find the odd coin among the most number of coins you can distinguish with that many weighings.

For example, after you compile it, type "a.out 3" to get directions on how to solve the classic "12 coins" problem.

WARNING: A few lines in the "do_output()" function are longer than 80 columns, and might get wrapped somewhere between me and you. Look out for this before you compile.

Tom Magliery mag@ncsa.uiuc.edu

- /

/*

Date: Fri, 06 Sep 96 07:08:25 GMT From: jcampbel@vitgsysa.telecom.com.au (James A. Campbell) Subject: Re: 12 coins

Here is the solution to the 12 coins question.

Having missed the question, I presume this is the old "12 objects, 11 weigh the same, the 12th has a different weight, 3 weighings using a beam balance" question.

This solution is generic for any number of objects which is equal to (3^n - 3)/2 objects. In this case n=3, ie #objects = (3^3 - 3)/2.

Take the set of trinary (0,1,2) integers with n digits (000, 001, 002, 010, .. 222). Discard those where each of the digits is the same (000, 111, 222) or where the first change is to the next lower digit or from 0 to 2 (002, 02x, 110, 10x, 221, 21x). You will now be left with the appropriate number of numbers (001, 010, 011, 012, 112, 120, 121, 122, 220, 200, 201 and 202). Attach each to an object (obviously, a unique matching).

In the ith weighing, place all objects whose ith digit is '0' in the left hand pan, and those whose ith digit is '2' in the right hand pan (for the first wighing 001, 010, 011 and 012 in the LH pan and 220, 200, 201 and 202 in the RH pan.) Record the "lighter" pan and the "heavier" pan. (for the first weighing if the RH pan is lighter, then record '2' as the first digit of the lighter pan, and '0' as the first digit of the heavier pan).

After n weighings you will have an n-digit lighter pan number and an n-digit heavier pan number. One of these will be one of your attached numbers (the other will be a discarded number). It will identify the differently-weighed object and whether it is lighter or heavier.

James Campbell Telstra Corporation jcampbel@vitgsysa.telecom.com.au

/

- include <stdio.h>
- define BOOL int
- define TRUE 1
- define FALSE 0

char* get_first_obj_name (int); char* get_last_obj_name (int); char* get_next_obj_name (char*, int); BOOL valid_obj_name (char*, int); void do_output (int);

main (int argc, char** argv) {

int num_weighings;

/* take care of boring user-input data checking stuff */ if (argc < 2) {

printf ("Correct usage is: '%s

number-of-weighings?'\n", *argv); exit (37); }num_weighings = atoi (argv

1?); if (!num_weighings) {printf ("Well, that's a bit silly, isn't it?\n"); exit (37); }

if (num_weighings == 1) {

printf ("You can't distinguish any objects with only 1 weighing!\n"); exit (37); }

/* all the fun stuff happens here */ do_output (num_weighings);

exit (0);

}

/*

- /

char* get_first_obj_name (int name_size) {

/* This function creates a string of length "name_size" consisting **/
/** of all 0's. It is used to get the first string in a sequence of **/
/** ternary numbers. */

char* firstname = (char*) malloc (name_size*sizeof(char) + 1); int i; for (i=0; i<name_size; i++)

firstname

i? = '0';firstname

name_size? = '\0'; return firstname;

}

/*

- /

char* get_last_obj_name (int name_size) {

/* This function creates a string of length "name_size" consisting of **/
/** all 2's. It is used to determine the last string in a sequence of **/
/** ternary numbers. */

char* lastname = (char*) malloc (name_size*sizeof(char) + 1); int i; for (i=0; i<name_size; i++)

lastname

i? = '2';lastname

name_size? = '\0'; return lastname;

}

/*

- /

char* get_next_obj_name (char* name, int name_size) {

/* Given a ternary string and its length, this function generates the **/
/** next string in sequence. It does not check for "overflow", i.e., **/
/** terrible things will happen if it is passed a string of all 2's. */

int current_digit;

/* first, check the last digit */ if (name

name_size-1? != '2')else {

current_digit = name_size-1; do {

name

current_digit? = '0'; current_digit--;} while (name

current_digit? == '2'); namecurrent_digit? = namecurrent_digit? + 1; }return;

}

/*

- /

BOOL valid_obj_name (char* name, int name_size) {

/* This function is used to validate a ternary string according to **/
/** the rules laid out in the description of the problem by James **/
/** Campbell. In particular, if the string consists of all the same **/
/** digit, or if the first change in the string is to the next lower **/
/** digit, or from 0 to 2, the function returns FALSE. Otherwise the **/
/** function returns TRUE. */

int i; int first_diff;

first_diff = name_size; for (i=0; i<name_size-1; i++)

first_diff = i; break; }

if (first_diff == name_size)

return FALSE;

if (((name first_diff? == '0') && (namefirst_diff+1? == '2')) |return FALSE;

return TRUE;

}

/*

- /

void do_output (int num_weighings) {

/* This is the fun part. */

char* name = (char*) malloc (num_weighings*sizeof(char) + 1); char* firstname = get_first_obj_name (num_weighings); char* lastname = get_last_obj_name (num_weighings); int weigh_num; int i, num_objs;

num_objs = 1; for (i=1; i<

num_weighings; i++) num_objs *3; num_objs = (num_objs - 3) / 2;printf ("%d weighings can be used to find the odd one out of %d objects\n",

num_weighings, num_objs);

printf ("as follows:\n\n");

printf ("1. Assign the following \"magic number\" labels to the objects:\n"); printf ("\n\t");

strcpy (name, firstname); while (strcmp (name, lastname)) {

if (valid_obj_name (name, num_weighings))

printf ("%s ", name);

get_next_obj_name (name, num_weighings); }

printf ("\n");

printf ("\n"); printf ("2. Initialize two character strings LIGHT and HEAVY to the empty\n"); printf ("string.\n"); printf ("\n"); printf ("3. Do the following %d weighings, recording the results as follows:\n",

num_weighings);

printf ("If the pans balance, append '1' to both LIGHT and HEAVY.\n"); printf ("If the left side is lighter, append '0' to LIGHT and '2' to HEAVY.\n"); printf ("If the right side is lighter, append '2' to LIGHT and '0' to HEAVY.\n");

for (weigh_num=1; weigh_num<=num_weighings; weigh_num++) {

printf ("\n"); printf ("\tWeighing #%d:\n", weigh_num); printf ("\t\t");

strcpy (name, firstname); while (strcmp (name, lastname)) {

if (valid_obj_name (name, num_weighings))

if (name

weigh_num-1? == '0')printf ("%s ", name);

get_next_obj_name (name, num_weighings); }

printf (" vs ");

strcpy (name, firstname); while (strcmp (name, lastname)) {

if (valid_obj_name (name, num_weighings))

if (name

weigh_num-1? == '2')printf ("%s ", name);

get_next_obj_name (name, num_weighings); }

printf ("\n"); }

printf ("\n"); printf ("4. After %d weighings, either LIGHT or HEAVY will exactly match one\n",

num_weighings);

printf ("of the \"magic numbers\". The object that has that magic number is the\n"); printf ("odd one, and its fault is shown by whether LIGHT or HEAVY matched.\n");

return;

}