6.042/18.] Mathematics for Computer Science March 16, 2005 Srini devadas and Eric Lehman Notes for Recitation 11 The Quest An explorer is trying to reach the Holy Grail, which she believes is located in a desert shrine d days walk from the nearest oasis. In the desert heat, the explorer must drink continuously. She can carry at most 1 gallon of water, which is enough for 1 day. However, she is free to create water caches out in the desert For example, if the shrine were 2/3 of a days walk into the desert, then she could recover the Holy Grail with the following strategy. She leaves the oasis with 1 gallon of water, travels 1 /3 day into the desert, caches 1/3 gallon, and then walks back to the oasis- arriving just as her water supply runs out. Then she picks up another gallon of water at the oasis, walks 1/3 day into the desert, tops off her water supply by taking the 1/3 gallon in her cache, walks the remaining 1/3 day to the shine, grabs the Holy Grail, and then walks for 2/3 of a day back to the oasis- again arriving with no water to spare But what if the shrine were located farther away? (a) What is the most distant point that the explorer can reach and return from if she takes only 1 gallon from the oasis. Solution. At best she can walk 1 /2 day into the desert and then walk back. (b)What is the most distant point the explorer can reach return if she takes only 2 gallons from the oasis? No proof is required; just do the best you can Solution. The explorer walks 1/4 day into the desert, drops 1/2 gallon, then walk home.Next, she walks 1/4 day into the desert picks up 1/4 gallet l(gallon from her cache and walks home. Thus, her maximum distance from the oasis is 3/ 4 of a day s walk (c)What about 3 gallons?(Hint: First, try to establish a cache of 2 gallons plus enough water for the walk home as far into the desert as possible. Then use this cache as a springboard for your solution to the previous part. Solution. Suppose the explorer makes three trips 1/6 day into the desert, dropping 2/3 gallon off units each time. On the third trip, the cache has 2 gallons of water, and the explorer still has 1 6 gallon for the trip back home. So, instead of returning6.042/18.062J Mathematics for Computer Science March 16, 2005 Srini Devadas and Eric Lehman Notes for Recitation 11 1 The Quest An explorer is trying to reach the Holy Grail, which she believes is located in a desert shrine d days walk from the nearest oasis. In the desert heat, the explorer must drink continuously. She can carry at most 1 gallon of water, which is enough for 1 day. However, she is free to create water caches out in the desert. For example, if the shrine were 2/3 of a day’s walk into the desert, then she could recover the Holy Grail with the following strategy. She leaves the oasis with 1 gallon of water, travels 1/3 day into the desert, caches 1/3 gallon, and then walks back to the oasis— arriving just as her water supply runs out. Then she picks up another gallon of water at the oasis, walks 1/3 day into the desert, tops off her water supply by taking the 1/3 gallon in her cache, walks the remaining 1/3 day to the shine, grabs the Holy Grail, and then walks for 2/3 of a day back to the oasis— again arriving with no water to spare. But what if the shrine were located farther away? (a) What is the most distant point that the explorer can reach and return from if she takes only 1 gallon from the oasis.? Solution. At best she can walk 1/2 day into the desert and then walk back. (b) What is the most distant point the explorer can reach and return form if she takes only 2 gallons from the oasis? No proof is required; just do the best you can. Solution. The explorer walks 1/4 day into the desert, drops 1/2 gallon, then walks home. Next, she walks 1/4 day into the desert, picks up 1/4 gallon from her cache, walks an additional 1/2 day out and back, then picks up another 1/4 gallon from her cache and walks home. Thus, her maximum distance from the oasis is 3/4 of a day’s walk. (c) What about 3 gallons? (Hint: First, try to establish a cache of 2 gallons plus enough water for the walk home as far into the desert as possible. Then use this cache as a springboard for your solution to the previous part.) Solution. Suppose the explorer makes three trips 1/6 day into the desert, dropping 2/3 gallon off units each time. On the third trip, the cache has 2 gallons of water, and the explorer still has 1/6 gallon for the trip back home. So, instead of returning