You are given 12 identical-looking coins, one of which is counterfeit and weighs slightly more or less (you...

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
=L= T heavy
=LR F light
==L C light
===
==R C heavy
=RL F heavy
=R= T light
=RR N heavy
RLL E heavy
RL= D light
RLR
R=L K heavy
R== L heavy
R=R A light
RRL O light
RR= M light
RRR I heavy

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')
        name[name_size-1] = name[name_size-1] + 1;

    else {
        current_digit = name_size-1;
        do {
            name[current_digit] = '0';
            current_digit--;
        } while (name[current_digit] == '2');
        name[current_digit] = name[current_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++)
        if (name[i] != name[i+1]) {
            first_diff = i;
            break;
            }

    if (first_diff == name_size)
        return FALSE;
    if (((name[first_diff] == '0') &amp;&amp; (name[first_diff+1] == '2')) ||
            ((name[first_diff] - name[first_diff+1]) == 1))
        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;
}