Thursday, September 11, 2008

12 Coins Problem with Non-Adaptive Weighing

I recently came across a problem on the net which went as follow:

You are given 12 coins, one of which is defective. The defective coin is either lighter or heavier than the rest of the coins. You are given a balance scale and are told to determine which coin is defective by using three non-adaptive weighs. This means that you cannot change which coins you decide to weigh based on the any of the previous measurements. Meaning there is nothing like this allowed:

IF COIN X weighs the same as COIN Y
THEN WEIGH COIN Z against COIN W

Instead you must basically come up with your plan of attack before weighing any coins, and then not stray from that plan once you've started.

Here is the solution that I came up with:

KEY:
L - Left side
R - Right side
U - Unused
H - Heavy
F - Light

Notes:
When I write something like this:
{1 2 3 4 5 6 7 8}:{H F}

It means that the defective coin could be 1..8 and I don't know if it is Heavy or Light yet

When I write something like this:
{1}:{F}

It means that the defective coin is 1 and it is Light.

/************FIRST WEIGH******************************************/

L {1 2 3 4}     R {5 6 7 8}     U {9 10 11 12}

At this point:
     IF unbalanced THEN {1 2 3 4 5 6 7 8}:{H F}
     ELSE {9 10 11 12}:{H F}

/************SECOND WEIGH*****************************************/

L {6 2 10 12}     R {5 1 7 11}     U {3 4 8 9}

At this point:
     IF {1 2 3 4 5 6 7 8} THEN
          IF balanced THEN {3 4 8}:{H F}
          ELSE IF unbalanced and in the opposite position
               as the first weigh THEN {6 1}:{H F}
          ELSE IF unbalanced and in the same position
               as the first weigh THEN {5 2 7}:{H F}
     ELSE {9 10 11 12}
          IF balanced THEN {9}:{H F}
          ELSE {10 11 12}:{H F}

/************THIRD WEIGH******************************************/

L {7 3 9 10}     R {6 4 5 12}     U {1 11 2 8}

At this point:
     IF {6 1} THEN
          IF balanced
               IF R was light (second weigh) THEN {1}:{F}
               ELSE {1}:{H}
          ELSE
               IF R is light THEN {6}:{F}
               ELSE {6}:{H}
     IF {9} THEN
          IF L is light THEN {9}:{F}
          ELSE {9}:{H}
     IF {5 2 7} THEN
          IF balanced THEN
               IF L was light (second weigh) THEN {2}:{F}
               ELSE {2}:{H}
          ELSE
               IF R is heavy THEN
                    IF R was heavy (second weigh) THEN {5}:{H}
                    ELSE {7}:{F}
               ELSE
                    IF R was light (second weigh) THEN {5}:{F}
                    ELSE {7}:{H}
     IF {3 4 8} THEN
          IF balanced THEN
               IF R was light (first weigh) THEN {8}:{F}
               ELSE {8}:{H}
          ELSE
               IF L is heavy THEN
                    IF L was heavy (first weigh) THEN {3}:{H}
                    ELSE {4}:{H}
               ELSE
                    IF L was light (first weigh) THEN {3}:{F}
                    ELSE {4}:{F}
     If {10 11 12} THEN
          IF balanced THEN
               IF R was heavy (second weigh) THEN {11}:{H} ELSE {11}:{F}
          ELSE
               IF L is heavy THEN
                    IF L was heavy (second weigh) THEN {10}:{H}
                    ELSE {12}:{F}
               ELSE
                    IF L was light {second weight} THEN {10}:{F}
                    ELSE {12}:{H}

No comments: