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}
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment