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 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 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 14 IS THE LEAST NUMBER OF TRIPS TO FIND OUT THE SOLUTION. THE EASIEST WAY TO DO THIS WOULD BE TO START FROM THE FIRST FLOOR AND DROP THE COCONUT. IF IT DOESN'T BREAK, MOVE ON TO THE NEXT FLOOR. IF IT DOES BREAK, THEN WE KNOW THE MAXIMUM FLOOR THE COCONUT WILL SURVIVE. IF WE CONTINUE THIS PROCESS, WE WILL EASILY FIND OUT THE MAXIMUM FLOORS THE COCONUT WILL SURVIVE WITH JUST ONE COCONUT. SO THE MAXIMUM NUMBER OF TRIES IS 100 FOR 100 FLOORS. THERE IS A BETTER WAY. LET'S START AT THE SECOND FLOOR. IF THE COCONUT BREAKS, THEN WE CAN USE THE SECOND COCONUT TO GO BACK TO THE FIRST FLOOR AND TRY AGAIN. IF THE 1ST COCONUT DOES NOT BREAK, THEN WE CAN GO AHEAD AND TRY ON THE 4TH FLOOR (IN MULTIPLES OF 2). IF IT EVER BREAKS, SAY AT FLOOR N, THEN WE KNOW IT SURVIVED FLOOR N-2. THAT LEAVES US WITH JUST FLOOR N-1 TO TRY WITH THE SECOND COCONUT. WITH THIS METHOD, THE MAXIMUM TRIES IS 51. IT OCCURS WHEN THE COCONUT SURVIVES 98 FLOORS. IT WILL TAKE 50 TRIES TO REACH FLOOR 100 AND ONE MORE COCONUT TO TRY ON THE 99TH FLOOR SO THE TOTAL IS 51 TRIES. NOW, FOR THE ULTIMATE METHOD. INSTEAD OF TAKING EQUAL INTERVALS, WE CAN DECREASE THE NUMBER OF FLOORS BY ONE LESS THAN THE PREVIOUS ONE. FOR EXAMPLE, LET'S FIRST TRY AT FLOOR 14. IF IT BREAKS, THEN WE NEED 13 MORE TRIES TO FIND THE SOLUTION. IF IT DOESN'T BREAK, THEN WE SHOULD TRY FLOOR 27 (14 + 13). IF IT BREAKS, WE NEED 12 MORE TRIES TO FIND THE SOLUTION. SO THE INITIAL 2 TRIES PLUS THE ADDITIONAL 12 TRIES WOULD STILL BE 14 TRIES IN TOTAL. IF IT DOESN'T BREAK, WE CAN TRY 39 (27 + 12) AND SO ON. USING 14 AS THE INITIAL FLOOR, WE CAN REACH UP TO FLOOR 105 (14 + 13 + 12 + ... + 1) BEFORE WE NEED MORE THAN 14 TRIES. SINCE WE ONLY NEED TO COVER 100 FLOORS, 14 TRIES IS SUFFICIENT TO FIND THE SOLUTION. COCONUT DROP COUNTFLOOR 114 227 339 450 560 669 777 884 990 1095 1199 12100 THEREFORE, 14 IS THE LEAST NUMBER OF TRIES TO FIND OUT THE SOLUTION