Riddler Classic Puzzle 11-12-2021

One day you stumble across a magic genie, who says that if you play a simple game with him, you could win fabulous riches. You take the genie up on his offer, and he hands you a stick of length 1. He says that behind his back is another stick, with a random length between 0 and 1 (chosen uniformly over that interval).

Next, you must break your stick into two pieces and present one of those pieces to the genie. If that piece is longer than the genie’s hidden stick, then you win a prize of $1 million times the length of your remaining piece. For example, if you present to the genie a length of 0.4, and that’s longer than the genie’s stick, then you win $1 million times 0.6, or $600,000. However, if the genie’s stick is longer, then you win nothing.

Being a regular reader of The Riddler, you crunch some numbers and prepare to break your stick in half. But then you have a thought. You ask the genie if you can have more than one turn. For example, if you present the genie with a length of 0.4, but the genie’s stick is longer, can you break off a piece of the remaining length of 0.6 — say, a length of 0.5 — and then present that to the genie? To keep things fair, your winnings will still be proportional to the leftover length. So had the genie’s length indeed been between 0.4 and 0.5, your first and second guesses, then the remaining length would have been 0.1, and you would have won $100,000.

The genie doesn’t think any of this really matters and says you can have as many turns as you desire. If your goal is to maximize your expected winnings, what will your strategy be? And how much money would you expect to win on average?

 
FiveThirtyEight

SOLUTION

Consider a strategy of N cuts of lengths c1 c2 c3 ... cN

where

0  <  c1  <  c2  <  c3  <  ...  <  cN

and

c1  +  c2  +  c3  +  ...  +  cN  <  1


Then we show the expected value of this strategy is NO BETTER than a strategy of just ONE CUT of length cN (the longest cut)

Let's first compute the expected value of this N cut strategy:

   c1 (1 - c1)

+ (c2 - c1) (1 - c1 - c2)

+ (c3 - c2) (1 - c1 - c2 - c3)

.....

+ (cN-1 - cN-2) (1 - c1 - c2 - c3 - ... - cN-1)

+ (cN - cN-1) (1 - c1 - c2 - c3 - ... - cN-1 - cN)


Due to its partial telescoping nature, the above sum can be simplified to its more convenient form:


  cN - cN^2

- c1 (cN - c2)

- c2 (cN - c3)

- c3 (cN - c4)

 ......

- cN-2 (cN - cN-1)


We see easily only the term cN - cN^2 is positive, while all the other terms are negative due to the initial condition:


0  <  c1  <  c2  <  c3  <  ...  <  cN


Thus, the expected value of the N cut strategy is less than cN - cN^2 = cN (1 - cN), which is just the expected value of one cut of length cN.

And the maximum value of cN (1 - cN)  =  1/4  when  cN = 1/2  (half the stick)

So the maximum expected winnings are 1/4 * $ 1 M = $ 250 K