Lily Pads

A frog needs to jump across 20 lily pads. He starts on the shore (Number 0) and ends precisely on the last lily pad (Number 20). He can jump one or two lily pads at a time. How many different ways can he reach his destination? What if he can jump one, two or three at a time? Or four? Five? Six? Etc. [Solution]

Showcase Showdown

On the brilliant and ageless game show “The Price Is Right,” there is an important segment called the Showcase Showdown. Three players step up, one at a time, to spin an enormous, sparkling wheel. The wheel has 20 segments at which it can stop, labeled from five cents up to one dollar, in increments of five cents. Each player can spin the wheel either one or two times. The goal is for the sum of one’s spins to get closer to one dollar than the other players, without going over. (Any sum over a dollar loses. Ties are broken by a single spin of the wheel, where the highest number triumphs.) For what amounts should the first spinner stop after just one spin, assuming the other two players will play optimally? [Solution]

Oracle Foolery

You must build a very specific tower out of four differently colored pieces that can be stacked in any order. But when you start building, you don’t know what the correct order is. Upon assembling the pieces in some order, you can consult an architectural oracle (he goes by Frank) who will inform you if zero, one, two or all four pieces of the tower are in the correct position. Your tower doesn’t count as finished until the oracle confirms your solution is correct. How many times should you have to consult the oracle, in the worst case, to assemble the tower correctly? [Solution]

Two Levers

One hundred prisoners are put into 100 completely isolated cells, numbered 1 to 100. Once they are in their cells, they cannot communicate with each other in any way. They are taken by the warden one at a time, but in no particular order, to a special room, Cell 0, in which there are two levers. As the prisoners enter the room, each lever is either up or down, but the levers’ starting positions are unknown. When in the room, a prisoner must flip exactly one of the levers. At any point, any prisoner may declare to the warden that all of the prisoners have been to the room. (The warden will take prisoners to the room indefinitely until someone makes a guess.) If the prisoner is correct, they are all released. If not, they are all executed. Knowing these rules, what strategy can the prisoners devise beforehand that will guarantee their release? How many trips to Cell 0 will it take on average before they are released? [Solution]

Optimal Coinball

Coinball is a contest where two players take turns trying to call a fair coin toss. The game lasts for 100 total tosses, 50 tosses for each player. On each toss, the player calling it announces either “heads” or “tails” and either “rush” or “pass.” If he says “rush,” he gets one point if he calls the toss correctly, and his opponent gets one point if the call is incorrect. Saying “pass” means the toss is worth two points to the caller if he calls the toss correctly and two points to his opponent if he does not. At the end, the player with the most points wins. (The margin of victory is irrelevant; in Coinball, league rankings are based only on wins, with a draw counting as half a win.) If you know your opponent always calls “rush” and you follow the optimal strategy given that knowledge, what are your chances of winning? What if you know your opponent always calls “pass”? If you and your opponent both play optimally, is it better to go first? Or to go second and therefore get the last call? Extra credit: Put your Monte-Carlo simulations away and try to determine the win probabilities to 10 digits of precision. [Solution]