Solution to Riddle of the Week: The Peppermint Patty Problem
This is a solution to This Peppermint Patty Riddle Is Practically Impossible, part of our Riddle of the Week series.
This Pepperminty Patty Riddle Is Practically Impossible
Problem
You’re facing your friend, Caryn, in a “candy-off,” which works as follows: There’s a pile of 100 caramels and one peppermint patty. You and Caryn will go back and forth taking at least one and no more than five caramels from the candy pile in each turn. The person who removes the last caramel will also get the peppermint patty. And you love peppermint patties.
Suppose Caryn lets you decide who goes first. Who should you choose in order to make sure you win the peppermint patty?
Solution
The best way to approach this problem is to think backwards.
Let’s suppose Caryn faces five or fewer caramels in the pile on her turn. Then she can take them all, and will win the peppermint patty. So you need to make sure Caryn never faces a pile with five or fewer caramels. But how about six?
If Caryn starts a turn with six caramels in front of her, she’ll have to take one to five caramels, leaving you with the win. Alternatively, if she starts a turn with seven, eight, nine, 10, or 11 caramels, she can take just enough to leave you with six, which would ensure a win for her.
So you want Caryn to face six caramels in front of her. You’ll definitely be able to do that if she faces 12 caramels in her prior turn. From that turn, she’ll leave you with seven, eight, nine, 10, or 11 caramels, from which you can take away just enough to leave her with six.
You can be sure to leave Caryn with 12 caramels on a turn if and only if you leave her with 18 caramels on her previous turn. And you can leave her with 18 caramels, if and only if you leave her with 24 caramels on the turn before that. You may see the pattern now: You need Caryn to face a multiple of six caramels in each turn.
Now, 100 is not a multiple of six, which means you shouldn’t let Caryn go first. In fact, the closest multiple of six that’s under 100 is 96. Therefore, you should go first and take four caramels on your first turn, leaving Caryn facing a pile with 96 caramels.
No matter what Caryn takes on her first turn, make sure to leave her with 90 caramels for her second turn, 84 caramels for her third turn, 78 for her fourth turn, and … six for her 16th and last turn. She’ll then take some amount of caramels, leaving you with the ability to take the last caramel and the peppermint patty.
There’s one interesting side effect of your strategy: Caryn can do quite well in terms of the number of caramels she receives by taking the maximum number (five) in each turn. Since she has 16 turns, she’ll end up with 16 x 5 = 80 caramels, whereas you’ll end up with only 20. You better really like that peppermint patty!
Want to talk about brain teasers or try to out-riddle the riddler? Find Laura on Twitter at @LauraFeiveson.
You Might Also Like
