Sunday, February 10, 2008

Lantern and Rope Riddles

A posting over the summer about riddles was warmly received by a few people who talked to me, so I am posting another set of riddles given to me by Paul, who passes them out like hard candies. Answers are written in light blue, so please highlight the text with your mouse to see the text more clearly.


A great pharoah of Egypt wanted to send 100 lanterns down the Nile River, and he set 100 servants to do a certain task. The lanterns would be floated down, and the first servant would light each one. The second servant would extinguish the 2nd, 4th, 6th (every even-numbered) lantern, while a third servant would find a lantern either "on"/"off" and then extinguish/relight every 3rd lantern. The fourth servant would look at every 4th lantern and also extinguish/relight the lantern depending on its present state...and so on until the 100th servant either extinguishes or relights the 100th lantern.

By the end of the ceremony, which lanterns are lit and which ones are extinguished?

ANSWER: There's an easy way and a hard way. The hard way is to make a chart and map out the pattern of the first 10 or so lanterns as they progress down the Nile. After the 10th servant has made his move, none of the succeedingly servants will touch the first 10 lanterns and you can determine their final state. You will find that lanterns 1, 4, and 9 will remain lit...and then find since 1+3 = 4, and 4+5 = 9, then why not add 9+7 = 16? By using this pattern, you will find that lanterns 1, 4, 9, 16, and 25 will remain lit. What is the pattern? All the lanterns are squares!

"But WHY?" you ask. The easy solution is to realize that, say, for lantern 20, that it will be touched by servants 1, 2, 4, 5, 10, and 20 (factors of 20, as Paul reminds), which is an even number of servants, and hence the lantern will be ultimately extinguished. However, for lantern 25, which is a square, the lantern will be touched by servants 1, 5, and 25, which will always be an ODD number since squares will always have an odd number of factors -- and thus lantern 25 will remain lit. Therefore, by the end of the ceremony, only lanterns which are square numbers will be lit!


Paul made up this variation of the lantern riddle himself in half a second.
Pretend the same scenario of 100 lanterns and 100 servants. The first servant lights each lantern as usual, but this time EACH SERVANT will meddle with the first lantern and continue his pattern. So the 2nd servant would extinguish lamps 1, 3, 5, etc. The third servant would light/extinguish lamps 1, 4, 7, etc. And the fourth servant would light/extinguish lamps 1, 5, 9, etc.

By the end of the ceremony, which lanterns are lit and which ones are extinguished?

ANSWER: The hard way is to make another chart and determine which lanterns are lit and extinguished, as before, which will allow you to find that lanterns 2, 5, and 10 will be lit by the end of the ceremony. This pattern is square numbers + 1, so all lanterns that are a square number + 1 will be lit by the end.

BUT WHY? Since every servant touches the first lantern, regard the first lantern as LANTERN zero. The pattern of lighting has been shifted over 1 position, so that it will always be square+1.


A semi-easier question supposedly asked by interviewers at JP Morgan. Pretend that you have TWO ropes which do NOT burn at a constant rate throughout the rope, but are cut to ensure that they will burn for exactly 1 hour each. Using only these two ropes, how do you measure out 45 minutes?

ANSWER: Burning the rope at one end will measure out 1 hour, but burning a rope at both ends will measure out 30 minutes, despite the variable burn rates. Start by lighting Rope 1 at one end and Rope 2 at both ends. When Rope 2 burns out, 30 minutes have elapsed -- and then quickly light the other end of Rope 1 so that you will get half of the remaining 30 minutes. Since 30 + 15 = 45, you will measure out 45 minutes. :)


Jacqueline said...

AWESOME, Steph!! I love these. So good. Thanks for sending me here - I think you had sent it long ago and I somehow misfiled the link. :)

Love you love you!

quintic said...

For a bonus in the rope riddle, what hidden assumption regarding the burn rate is needed to conclude that when lit at both ends the first rope burns out in 30 minutes?