A N
_ L G _ R _ T H M
T H _ T
G _ _ R _ N T _ _ S
T H _
B _ L L
W _ L L
R _ N G
_ N
_ T
M _ S T
F _ V _
T _ R N S
_ S
_ S
F _ L L _ W S :
O N
T H _
F _ R S T
T _ R N
C H _ _ S _
_
D _ _ G _ N _ L L Y
_ P P _ S _ T _
P _ _ R
_ F
G L _ S S _ S
_ N D
T _ R N
B _ T H
G L _ S S _ S
_ P .
O N
T H _
S _ C _ N D
T _ R N
C H _ _ S _
T W _
_ D J _ C _ N T
G L _ S S _ S .
A T
L _ _ S T
_ N _
W _ L L
B _
_ P
_ S
_
R _ S _ L T
_ F
T H _
P R _ V _ _ _ S
S T _ P .
I F
T H _
_ T H _ R
_ S
D _ W N ,
T _ R N
_ T
_ P
_ S
W _ L L .
I F
T H _
B _ L L
D _ _ S
N _ T
R _ N G ,
T H _ N
T H _ R _
_ R _
N _ W
T H R _ _
G L _ S S _ S
_ P
_ N D
_ N _
D _ W N .
O N
T H _
T H _ R D
T _ R N
C H _ _ S _
_
D _ _ G _ N _ L L Y
_ P P _ S _ T _
P _ _ R
_ F
G L _ S S _ S .
I F
_ N _
_ S
D _ W N ,
T _ R N
_ T
_ P
_ N D
T H _
B _ L L
W _ L L
R _ N G .
I F
B _ T H
_ R _
_ P ,
T _ R N
_ N _
D _ W N .
T H _ R _
_ R _
N _ W
T W _
G L _ S S _ S
D _ W N ,
_ N D
T H _ Y
M _ S T
B _
_ D J _ C _ N T .
O N
T H _
F _ _ R T H
T _ R N
C H _ _ S _
T W _
_ D J _ C _ N T
G L _ S S _ S
_ N D
R _ V _ R S _
B _ T H .
I F
B _ T H
W _ R _
_ N
T H _
S _ M _
_ R _ _ N T _ T _ _ N
T H _ N
T H _
B _ L L
W _ L L
R _ N G .
O T H _ R W _ S _
T H _ R _
_ R _
N _ W
T W _
G L _ S S _ S
D _ W N
_ N D
T H _ Y
M _ S T
B _
D _ _ G _ N _ L L Y
_ P P _ S _ T _ .
O N
T H _
F _ F T H
T _ R N
C H _ _ S _
_
D _ _ G _ N _ L L Y
_ P P _ S _ T _
P _ _ R
_ F
G L _ S S _ S
_ N D
R _ V _ R S _
B _ T H .
T H _
B _ L L
W _ L L
R _ N G .
T H _
P _ Z Z L _
C _ N
B _
G _ N _ R _ L _ S _ D
T _
N
G L _ S S _ S
_ N S T _ _ D
_ F
F _ _ R .
F _ R
T W _
G L _ S S _ S
_ T
_ S
T R _ V _ _ L L Y
S _ L V _ D
_ N
_ N _
T _ R N
B Y
_ N V _ R T _ N G
_ _ T H _ R
G L _ S S .
F _ R
T H R _ _
G L _ S S _ S
T H _ R _
_ S
_
T W _ - T _ R N
_ L G _ R _ T H M .
F _ R
F _ V _
_ R
M _ R _
G L _ S S _ S
T H _ R _
_ S
N _
_ L G _ R _ T H M
T H _ T
G _ _ R _ N T _ _ S
T H _
B _ L L
W _ L L
R _ N G
_ N
_
F _ N _ T _
N _ M B _ R
_ F
T _ R N S .
A
F _ R T H _ R
G _ N _ R _ L _ S _ T _ _ N
_ L L _ W S
K
G L _ S S _ S
( _ N S T _ _ D
_ F
T W _ )
_ _ T
_ F
T H _
N
G L _ S S _ S
T _
B _
_ X _ M _ N _ D
_ T
_ _ C H
T _ R N .
A N
_ L G _ R _ T H M
C _ N
B _
F _ _ N D
T _
R _ N G
T H _
B _ L L
_ N
_
F _ N _ T _
N _ M B _ R
_ F
T _ R N S
_ S
L _ N G
_ S
K
≥
( 1
−
1 ⁄ P
) N
W H _ R _
P
_ S
T H _
G R _ _ T _ S T
P R _ M _
F _ C T _ R
_ F
N Clue
AN ALGORITHM THAT GUARANTEES THE BELL WILL RING IN AT MOST FIVE TURNS IS AS FOLLOWS: ON THE FIRST TURN CHOOSE A DIAGONALLY OPPOSITE PAIR OF GLASSES AND TURN BOTH GLASSES UP. ON THE SECOND TURN CHOOSE TWO ADJACENT GLASSES. AT LEAST ONE WILL BE UP AS A RESULT OF THE PREVIOUS STEP. IF THE OTHER IS DOWN, TURN IT UP AS WELL. IF THE BELL DOES NOT RING, THEN THERE ARE NOW THREE GLASSES UP AND ONE DOWN. ON THE THIRD TURN CHOOSE A DIAGONALLY OPPOSITE PAIR OF GLASSES. IF ONE IS DOWN, TURN IT UP AND THE BELL WILL RING. IF BOTH ARE UP, TURN ONE DOWN. THERE ARE NOW TWO GLASSES DOWN, AND THEY MUST BE ADJACENT. ON THE FOURTH TURN CHOOSE TWO ADJACENT GLASSES AND REVERSE BOTH. IF BOTH WERE IN THE SAME ORIENTATION THEN THE BELL WILL RING. OTHERWISE THERE ARE NOW TWO GLASSES DOWN AND THEY MUST BE DIAGONALLY OPPOSITE. ON THE FIFTH TURN CHOOSE A DIAGONALLY OPPOSITE PAIR OF GLASSES AND REVERSE BOTH. THE BELL WILL RING. THE PUZZLE CAN BE GENERALISED TO N GLASSES INSTEAD OF FOUR. FOR TWO GLASSES IT IS TRIVIALLY SOLVED IN ONE TURN BY INVERTING EITHER GLASS. FOR THREE GLASSES THERE IS A TWO-TURN ALGORITHM. FOR FIVE OR MORE GLASSES THERE IS NO ALGORITHM THAT GUARANTEES THE BELL WILL RING IN A FINITE NUMBER OF TURNS. A FURTHER GENERALISATION ALLOWS K GLASSES (INSTEAD OF TWO) OUT OF THE N GLASSES TO BE EXAMINED AT EACH TURN. AN ALGORITHM CAN BE FOUND TO RING THE BELL IN A FINITE NUMBER OF TURNS AS LONG AS K ≥ (1 − 1⁄P )N WHERE P IS THE GREATEST PRIME FACTOR OF N 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 BRUCE TAKES 9 OF HIS 10 CIGARETTE BUTTS AND TURNS THEM INTO 3 CIGARETTES TOTAL (3 CIGARETTE BUTTS CAN BE TURNED INTO 1 CIGARETTE). HE SMOKES ALL THREE OF THESE, AND NOW HE HAS 4 CIGARETTE BUTTS. HE THEN TURNS 3 OF THE 4 CIGARETTE BUTTS INTO ANOTHER CIGARETTE AND SMOKES IT. HE HAS NOW SMOKED 4 CIGARETTES AND HAS 2 CIGARETTE BUTTS. AND FINALLY HE GOES AND BORROWS ONE OF TOM'S CIGARETTE BUTTS. WITH THIS CIGARETTE BUTT PLUS THE 2 HE ALREADY HAS, HE IS ABLE TO MAKE HIS 5TH CIGARETTE TO SMOKE. AFTER SMOKING IT, HE IS LEFT WITH 1 CIGARETTE BUTT, WHICH HE PUTS BACK IN TOM'S PILE SO THAT TOM WON'T FIND ANYTHING MISSING 7 RACES. LET'S NAME THE RACES R1 THROUGH R7. LET RXN REPRESENT A HORSE IN RACE X, FINISHING IN NTH PLACE. SO R32 REPRESENTS A HORSE THAT FINISHED 2ND PLACE IN THE 3RD RACE. GROUP THE 25 HORSES INTO 5 GROUPS OF 5 AND RACE THEM. THE 4TH AND 5TH PLACED HORSES OF EACH RACE CAN BE ELIMINATED SINCE THEY CANNOT MEET THE CRITERIA OF 3 FASTEST HORSES. WE ARE NOW LEFT WITH 15 HORSES (5 GROUPS OF 3 HORSES); 3 HORSES FROM EACH RACE. FOR THE 6TH RACE, RACE THE FASTEST HORSE (R11, R21, R31, R41, R51) FROM EACH OF THE FIRST 5 RACES. THE WINNER OF THE 6TH RACE IS THE FASTEST HORSE. THE 4TH AND 5TH PLACED HORSES FROM THE 6TH RACE CAN BE ELIMINATED INCLUDING ALL THE HORSES WITHIN THEIR RESPECTIVE GROUPS. FOR EXAMPLE, IF THE HORSE THAT CAME IN 4TH PLACE IS FROM R41, THE HORSES R42 AND R43 CAN BE ELIMINATED AS WELL. LET'S SAY FOR THE 6TH RACE, R11 CAME FIRST, R21 CAME 2ND AND R31 CAME 3RD. WE KNOW THAT R11 IS THE FASTEST HORSE. WE NOW NEED TO DETERMINE THE 2ND AND 3RD FASTEST HORSES. WE CAN NOW ALSO ELIMINATE THE HORSES R23, R32 AND R33. THIS WILL LEAVE US WITH FIVE HORSES FOR THE 7TH RACE - R12, R13, R21, R22 AND R31. THE 1ST AND 2ND PLACED HORSES IN THE 7TH RACE ARE THE 2ND AND 3RD FASTEST HORSES