Occasional Puzzles - Oaky, with a hint of...poison?
Reader Raphaël graduates from Harvard University this week with his PhD in Applied Mathematics. Congratulations, Raphaël!
Today’s Puzzle
As any good Frenchman would, Raphaël plans to have a party (appropriately socially distanced, bien sûr) with 1,000 bottles of fine French wine to celebrate. The party is planned for a week from today.
But there’s a problem. Raphaël has just discovered that one of the bottles is poisoned, and he doesn’t know which one. The poison has no test and no antidote; it is flavorless, odorless, and otherwise undetectable. Anyone who drinks from the poisoned bottle now will drop dead in exactly one week - just before the party.
Fortunately, Raphaël has ten loyal undergrads who are willing to sacrifice their lives to make sure the party goes off without a hitch. Using these ten undergrads and the mathematical superpowers granted by the conferral of his PhD, how does he identify the poisoned bottle before the party?
Sunday’s Puzzle - Adventures in Puzzlevania
In the magical land of Puzzlevania, you are on your way to visit your friend Theo for his 10th birthday. As is tradition in Puzzlevania, you want to bring him two cakes. You must cross seven bridges to get to his house and, unfortunately, each bridge has a troll under it.
Trolls in Puzzlevania are mean but not, like, super mean. Before each bridge crossing, the resident troll will take half of your cakes. But immediately after the crossing, he will feel bad and give you one cake back.
How many cakes do you need to start out with in order to arrive at Theo’s house with exactly two?
(Note that trolls do not accept half-cakes. If, at any time, you have an odd number of cakes, you will lose an extra half-cake. For example, if you come to a bridge with 9 cakes, the troll will take 5 of them before the crossing, not 4.5.)
[SPOILER] Answer to Sunday’s Puzzle
Two. But also 74. And 66. And 100. And, as it turns out, any number of cakes between 2 and 129 (inclusive).
The key here is to realize that any time you approach a bridge with 2 cakes, you leave with 2: the troll takes half of your cakes (1) and gives you 1 back. So, if at any point in your journey you leave a bridge with 2 cakes, you’re going to have 2 cakes all the way to Theo’s house.
For example, let’s say you start out with 16 cakes. You leave the first bridge with 9 cakes (16/2 + 1 = 9), the second with 5 cakes, the third with 3 cakes, the fourth with 2 cakes, and then you keep 2 cakes for the rest of the trip.
This works for all numbers of cakes up to 129. If you start with 130 cakes, you’ll reach Theo’s house with 3 cakes instead of 2.
For the mathematically inclined, the range of correct answers is 2 through (2^n)+1, where n is the number of bridges. Since you’re (roughly) halving the number of cakes at every bridge, the maximum number of cakes you can start out with is (roughly) the power of 2 that corresponds to the number of bridges.