M _ S T
P _ _ P L _
S _ _ M
T _
T H _ N K
T H _ T
T H _
T H _ N G
T _
D _
_ S
W _ _ G H T
S _ X
C _ _ N S
_ G _ _ N S T
S _ X
C _ _ N S ,
B _ T
_ F
Y _ _
T H _ N K
_ B _ _ T
_ T ,
T H _ S
W _ _ L D
Y _ _ L D
Y _ _
N _
_ N F _ R M _ T _ _ N
C _ N C _ R N _ N G
T H _
W H _ R _ _ B _ _ T S
_ F
T H _
_ N L Y
D _ F F _ R _ N T
C _ _ N .
A S
W _
_ L R _ _ D Y
K N _ W
T H _ T
_ N _
S _ D _
W _ L L
B _
H _ _ V _ _ R
T H _ N
T H _
_ T H _ R .
S _
T H _ T
T H _
F _ L L _ W _ N G
P L _ N
C _ N
B _
F _ L L _ W _ D ,
L _ T
_ S
N _ M B _ R
T H _
C _ _ N S
F R _ M
1
T _
1 2 .
F _ R
T H _
F _ R S T
W _ _ G H _ N G
L _ T
_ S
P _ T
_ N
T H _
L _ F T
P _ N
C _ _ N S
1 , 2 , 3 , 4
_ N D
_ N
T H _
R _ G H T
P _ N
C _ _ N S
5 , 6 , 7 , 8 .
T H _ R _
_ R _
T W _
P _ S S _ B _ L _ T _ _ S .
E _ T H _ R
T H _ Y
B _ L _ N C _ ,
_ R
T H _ Y
D _ N ' T .
I F
T H _ Y
B _ L _ N C _ ,
T H _ N
T H _
D _ F F _ R _ N T
C _ _ N
_ S
_ N
T H _
G R _ _ P
9 , 1 0 , 1 1 , 1 2 .
S _
F _ R
_ _ R
S _ C _ N D
W _ _ G H _ N G
W _
W _ _ L D
P _ T
1 , 2
_ N
T H _
L _ F T
P _ N
_ N D
9 , 1 0
_ N
T H _
R _ G H T .
I F
T H _ S _
B _ L _ N C _
T H _ N
T H _
D _ F F _ R _ N T
C _ _ N
_ S
_ _ T H _ R
1 1
_ R
1 2 .
W _ _ G H
C _ _ N
1
_ G _ _ N S T
1 1 .
I F
T H _ Y
B _ L _ N C _ ,
T H _
D _ F F _ R _ N T
C _ _ N
_ S
N _ M B _ R
1 2 .
I F
T H _ Y
D _
N _ T
B _ L _ N C _ ,
T H _ N
1 1
_ S
T H _
D _ F F _ R _ N T
C _ _ N .
I F
1 , 2
V S
9 , 1 0
D _
N _ T
B _ L _ N C _ ,
T H _ N
T H _
D _ F F _ R _ N T
C _ _ N
_ S
_ _ T H _ R
9
_ R
1 0 .
A G _ _ N ,
W _ _ G H
1
_ G _ _ N S T
9 .
I F
T H _ Y
B _ L _ N C _ ,
T H _
D _ F F _ R _ N T
C _ _ N
_ S
N _ M B _ R
1 0 ,
_ T H _ R W _ S _
_ T
_ S
N _ M B _ R
9 .
T H _ T
W _ S
T H _
_ _ S Y
P _ R T .
W H _ T
_ F
T H _
F _ R S T
W _ _ G H _ N G
1 , 2 , 3 , 4
V S
5 , 6 , 7 , 8
D _ _ S
N _ T
B _ L _ N C _ ?
T H _ N
_ N Y
_ N _
_ F
T H _ S _
C _ _ N S
C _ _ L D
B _
T H _
D _ F F _ R _ N T
C _ _ N .
N _ W ,
_ N
_ R D _ R
T _
P R _ C _ _ D ,
W _
M _ S T
K _ _ P
T R _ C K
_ F
W H _ C H
S _ D _
_ S
H _ _ V Y
F _ R
_ _ C H
_ F
T H _
F _ L L _ W _ N G
W _ _ G H _ N G S .
S _ P P _ S _
T H _ T
5 , 6 , 7 , 8
_ S
T H _
H _ _ V Y
S _ D _ .
W _
N _ W
W _ _ G H
1 , 5 , 6
_ G _ _ N S T
2 , 7 , 8 .
I F
T H _ Y
B _ L _ N C _ ,
T H _ N
T H _
D _ F F _ R _ N T
C _ _ N
_ S
_ _ T H _ R
3
_ R
4 .
W _ _ G H
4
_ G _ _ N S T
9 ,
_
K N _ W N
G _ _ D
C _ _ N .
I F
T H _ Y
B _ L _ N C _
T H _ N
T H _
D _ F F _ R _ N T
C _ _ N
_ S
3 ,
_ T H _ R W _ S _
_ T
_ S
4 .
N _ W ,
_ F
1 , 5 , 6
V S
2 , 7 , 8
D _ _ S
N _ T
B _ L _ N C _ ,
_ N D
2 , 7 , 8
_ S
T H _
H _ _ V Y
S _ D _ ,
T H _ N
_ _ T H _ R
7
_ R
8
_ S
_
D _ F F _ R _ N T ,
H _ _ V Y
C _ _ N ,
_ R
1
_ S
_
D _ F F _ R _ N T ,
L _ G H T
C _ _ N .
F _ R
T H _
T H _ R D
W _ _ G H _ N G ,
W _ _ G H
7
_ G _ _ N S T
8 .
W H _ C H _ V _ R
S _ D _
_ S
H _ _ V Y
_ S
T H _
D _ F F _ R _ N T
C _ _ N .
I F
T H _ Y
B _ L _ N C _ ,
T H _ N
1
_ S
T H _
D _ F F _ R _ N T
C _ _ N .
S H _ _ L D
T H _
W _ _ G H _ N G
_ F
1 , 5 ,
6
V S
2 , 7 , 8
S H _ W
1 , 5 , 6
T _
B _
T H _
H _ _ V Y
S _ D _ ,
T H _ N
_ _ T H _ R
5
_ R
6
_ S
_
D _ F F _ R _ N T
H _ _ V Y
C _ _ N
_ R
2
_ S
_
L _ G H T
D _ F F _ R _ N T
C _ _ N .
W _ _ G H
5
_ G _ _ N S T
6 .
T H _
H _ _ V _ _ R
_ N _
_ S
T H _
D _ F F _ R _ N T
C _ _ N .
I F
T H _ Y
B _ L _ N C _ ,
T H _ N
2
_ S
_
D _ F F _ R _ N T
L _ G H T
C _ _ N Clue
WHEN THE FIRST SERVANT COMES IN, THE KING SHOULD WRITE DOWN HIS NUMBER. FOR EACH OTHER SERVANT THAT REPORTS IN, THE KING SHOULD ADD THAT SERVANT'S NUMBER TO THE CURRENT NUMBER WRITTEN ON THE PAPER, AND THEN WRITE THIS NEW NUMBER ON THE PAPER. LET X BE THE NUMBER OF THE MISSING SERVANT AND Y BE THE NUMBER THAT THE KING HAS WRITTEN. ONCE THE FINAL SERVANT HAS REPORTED IN, THE NUMBER ON THE PAPER SHOULD EQUAL: Y = (1 + 2 + 3 + ... + 99 + 100) - X (1 + 2 + 3 + ... + 99 + 100) = 5050, SO WE CAN REPHRASE THIS TO SAY THAT THE NUMBER ON THE PAPER SHOULD EQUAL: Y = 5050 - X SO TO FIGURE OUT THE MISSING SERVANT'S NUMBER, THE KING SIMPLY NEEDS TO SUBTRACT THE NUMBER WRITTEN ON HIS PAPER FROM 5050: 5050 - Y = X FIRST WEIGHING: FOUR AGAINST FOUR SECOND WEIGHING: TWO AGAINST TWO THIRD WEIGHING: ONE AGAINST ONE LET'S NAME THE BALLS 1-12. FIRST WE WEIGH {1,2,3,4} ON THE LEFT AND {5,6,7,8} ON THE RIGHT. THERE ARE THREE SCENARIOS WHICH CAN ARISE FROM THIS. IF THEY BALANCE, THEN WE KNOW 9, 10, 11 OR 12 IS ODD. WEIGH {8, 9} AND {10, 11} (NOTE: 8 IS NOT ODD) IF THEY BALANCE, WE KNOW 12 IS THE ODD ONE. JUST WEIGH IT WITH ANY OTHER BALL AND FIGURE OUT IF IT IS LIGHTER OR HEAVIER. IF {8, 9} IS HEAVIER, THEN EITHER 9 IS HEAVY OR 10 IS LIGHT OR 11 IS LIGHT. WEIGH {10} AND {11}. IF THEY BALANCE, 9 IS ODD (HEAVIER). IF THEY DON'T BALANCE THEN WHICHEVER ONE IS LIGHTER IS ODD (LIGHTER). IF {8, 9} IS LIGHTER, THEN EITHER 9 IS LIGHT OR 10 IS HEAVY OR 11 IS HEAVY. WEIGH {10} AND {11}. IF THEY BALANCE, 9 IS ODD (LIGHTER). IF THEY DON'T BALANCE THEN WHICHEVER ONE IS HEAVIER IS ODD (HEAVIER). IF {1,2,3,4} IS HEAVIER, WE KNOW EITHER ONE OF {1,2,3,4} HEAVIER OR ONE OF {5,6,7,8} IS LIGHTER BUT IT IS GUARANTEED THAT {9,10,11,12} ARE NOT ODD. WEIGH {1,2,5} AND {3,6,9} (NOTE: 9 IS NOT ODD). IF THEY BALANCE, THEN EITHER 4 IS HEAVY OR 7 IS LIGHT OR 8 IS LIGHT. FOLLOWING THE LAST STEP FROM THE PREVIOUS CASE, WE WEIGH {7} AND {8}. IF THEY BALANCE, 4 IS ODD (HEAVIER). IF THEY DON'T BALANCE THEN WHICHEVER ONE IS LIGHTER IS ODD (LIGHTER). IF {1,2,5} IS HEAVIER, THEN EITHER 1 IS HEAVY OR 2 IS HEAVY OR 6 IS LIGHT. WEIGH {1} AND {2}. IF THEY BALANCE, 6 IS ODD (LIGHTER). IF THEY DON'T BALANCE THEN WHICHEVER ONE IS HEAVIER IS ODD (HEAVIER). IF {3,6,9} IS HEAVIER, THEN EITHER 3 IS HEAVY OR 5 IS LIGHT. WEIGH {5} AND {9}. THEY WON'T BALANCE. IF {5} IS LIGHTER, 5 IS ODD (LIGHTER). IF THEY BALANCE, 3 IS ODD (HEAVIER). IF {5,6,7,8} IS HEAVIER, IT IS THE SAME SITUATION AS IF {1,2,3,4} WAS HEAVIER. JUST PERFORM THE SAME STEPS USING 5,6,7 AND 8. WEIGH {5,6,1} AND {7,2,9} (NOTE: 9 IS NOT ODD). IF THEY BALANCE, THEN EITHER 8 IS HEAVY OR 3 IS LIGHT OR 4 IS LIGHT. WE WEIGH {3} AND {4}. IF THEY BALANCE, 8 IS ODD (HEAVIER). IF THEY DON'T BALANCE THEN WHICHEVER ONE IS LIGHTER IS ODD (LIGHTER). IF {5,6,1} IS HEAVIER, THEN EITHER 5 IS HEAVY OR 6 IS HEAVY OR 2 IS LIGHT. WEIGH {5} AND {6}. IF THEY BALANCE, 2 IS ODD (LIGHTER). IF THEY DON'T BALANCE THEN WHICHEVER ONE IS HEAVIER IS ODD (HEAVIER). IF {7,2,9} IS HEAVIER, THEN EITHER 7 IS HEAVY OR 1 IS LIGHT. WEIGH {1} AND {9}. IF THEY BALANCE, 7 IS ODD (HEAVIER). IF THEY DON'T BALANCE THEN 1 IS ODD (LIGHTER). NOTE: THERE ARE OTHER POSSIBLE SOLUTIONS TO THIS PROBLEM AS WELL 8 WEIGHINGS ARE REQUIRED TO FIND OUT THE HEAVY BALL. DIVIDE THE BALLS INTO 3 GROUPS OF 2187 BALLS EACH. PUT 2 GROUPS ON THE SCALE AND DETERMINE WHICH GROUP IS HEAVIER. IF BOTH GROUPS ARE EQUAL IN WEIGHT, THE HEAVIER BALL IS IN THE 3RD GROUP. REPEAT THE PROCESS BY BREAKING THE GROUP WITH THE HEAVIER BALL INTO 3 SMALLER GROUPS OF BALLS AGAIN. FOR THE 2ND ROUND, EACH GROUP WILL HAVE 729 (2187 / 3 ) BALLS EACH. THIS PROCESS HAS TO BE REPEATED 8 TIMES. 1ST WEIGHING - 6561 BALLS ARE DIVIDED INTO 3 GROUPS OF 2187 BALLS EACH. 2ND WEIGHING - 2187 BALLS ARE DIVIDED INTO 3 GROUPS OF 729 BALLS EACH. 3RD WEIGHING - 729 BALLS ARE DIVIDED INTO 3 GROUPS OF 243 BALLS EACH. 4TH WEIGHING - 243 BALLS ARE DIVIDED INTO 3 GROUPS OF 81 BALLS EACH. 5TH WEIGHING - 81 BALLS ARE DIVIDED INTO 3 GROUPS OF 27 BALLS EACH. 6TH WEIGHING - 29 BALLS ARE DIVIDED INTO 3 GROUPS OF 9 BALLS EACH. 7TH WEIGHING - 9 BALLS ARE DIVIDED INTO 3 GROUPS OF 3 BALLS EACH. 8TH WEIGHING - 3 BALLS ARE DIVIDED INTO 3 GROUPS OF 1 BALL EACH MOST PEOPLE SEEM TO THINK THAT THE THING TO DO IS WEIGHT SIX COINS AGAINST SIX COINS, BUT IF YOU THINK ABOUT IT, THIS WOULD YIELD YOU NO INFORMATION CONCERNING THE WHEREABOUTS OF THE ONLY DIFFERENT COIN. AS WE ALREADY KNOW THAT ONE SIDE WILL BE HEAVIER THAN THE OTHER. SO THAT THE FOLLOWING PLAN CAN BE FOLLOWED, LET US NUMBER THE COINS FROM 1 TO 12. FOR THE FIRST WEIGHING LET US PUT ON THE LEFT PAN COINS 1,2,3,4 AND ON THE RIGHT PAN COINS 5,6,7,8. THERE ARE TWO POSSIBILITIES. EITHER THEY BALANCE, OR THEY DON'T. IF THEY BALANCE, THEN THE DIFFERENT COIN IS IN THE GROUP 9,10,11,12. SO FOR OUR SECOND WEIGHING WE WOULD PUT 1,2 IN THE LEFT PAN AND 9,10 ON THE RIGHT. IF THESE BALANCE THEN THE DIFFERENT COIN IS EITHER 11 OR 12. WEIGH COIN 1 AGAINST 11. IF THEY BALANCE, THE DIFFERENT COIN IS NUMBER 12. IF THEY DO NOT BALANCE, THEN 11 IS THE DIFFERENT COIN. IF 1,2 VS 9,10 DO NOT BALANCE, THEN THE DIFFERENT COIN IS EITHER 9 OR 10. AGAIN, WEIGH 1 AGAINST 9. IF THEY BALANCE, THE DIFFERENT COIN IS NUMBER 10, OTHERWISE IT IS NUMBER 9. THAT WAS THE EASY PART. WHAT IF THE FIRST WEIGHING 1,2,3,4 VS 5,6,7,8 DOES NOT BALANCE? THEN ANY ONE OF THESE COINS COULD BE THE DIFFERENT COIN. NOW, IN ORDER TO PROCEED, WE MUST KEEP TRACK OF WHICH SIDE IS HEAVY FOR EACH OF THE FOLLOWING WEIGHINGS. SUPPOSE THAT 5,6,7,8 IS THE HEAVY SIDE. WE NOW WEIGH 1,5,6 AGAINST 2,7,8. IF THEY BALANCE, THEN THE DIFFERENT COIN IS EITHER 3 OR 4. WEIGH 4 AGAINST 9, A KNOWN GOOD COIN. IF THEY BALANCE THEN THE DIFFERENT COIN IS 3, OTHERWISE IT IS 4. NOW, IF 1,5,6 VS 2,7,8 DOES NOT BALANCE, AND 2,7,8 IS THE HEAVY SIDE, THEN EITHER 7 OR 8 IS A DIFFERENT, HEAVY COIN, OR 1 IS A DIFFERENT, LIGHT COIN. FOR THE THIRD WEIGHING, WEIGH 7 AGAINST 8. WHICHEVER SIDE IS HEAVY IS THE DIFFERENT COIN. IF THEY BALANCE, THEN 1 IS THE DIFFERENT COIN. SHOULD THE WEIGHING OF 1,5, 6 VS 2,7,8 SHOW 1,5,6 TO BE THE HEAVY SIDE, THEN EITHER 5 OR 6 IS A DIFFERENT HEAVY COIN OR 2 IS A LIGHT DIFFERENT COIN. WEIGH 5 AGAINST 6. THE HEAVIER ONE IS THE DIFFERENT COIN. IF THEY BALANCE, THEN 2 IS A DIFFERENT LIGHT COIN