{"id":3646,"date":"2023-05-21T10:47:06","date_gmt":"2023-05-21T15:47:06","guid":{"rendered":"https:\/\/laurentlessard.com\/bookproofs\/?p=3646"},"modified":"2023-05-22T14:56:27","modified_gmt":"2023-05-22T19:56:27","slug":"how-much-money-can-you-pull-out-of-a-hat","status":"publish","type":"post","link":"https:\/\/laurentlessard.com\/bookproofs\/how-much-money-can-you-pull-out-of-a-hat\/","title":{"rendered":"How much can you pull out of a hat?"},"content":{"rendered":"

This week’s Riddler Classic<\/a> is a strategy game about maximizing payout. What is the optimal strategy?<\/p>\n

\nYou start with just the number 1 written on a slip of paper in a hat. Initially, there are no other slips of paper in the hat. You will draw from the hat 100 times, and each time you draw, you have a choice: If the number on the slip of paper you draw is k, then you can either receive k dollars or add k higher numbers to the hat.<\/p>\n

For example, if the hat were to contain slips with the numbers 1 through 6 and you drew a 4, you could either receive $4 or receive no money but add four more slips numbered 7, 8, 9 and 10 into the hat. In either case, the slip with the number 4 would then be returned to the hat.<\/p>\n

If you play this game perfectly \u2014 that is, to maximize the total amount of money you\u2019ll receive after all 100 rounds \u2014 how much money would you expect to receive on average?\n<\/p><\/blockquote>\n

My solution:
\n[Show Solution]<\/a><\/p>\n

\nWhen we are playing the game, there are two relevant variables: (1) the number of slips of paper in the hat, and (2) the number of draws remaining. We will therefore define the following quantity:
\n\\[
\nw(n,t) = \\left\\{
\n\\begin{array}{l}
\n\\text{Amount we can expect to win from this point} \\\\
\n\\text{forward, if there are }n\\text{ slips of paper in the hat} \\\\
\n\\text{and we have }t\\text{ draws remaining, assuming} \\\\
\n\\text{optimal play for the rest of the game.}
\n\\end{array}
\n\\right\\}
\n\\]The problem is asking us to calculate $w(1,100)$. We will do this by calculating in order: $w(n,0)$, $w(n,1)$, and so on, using a process called dynamic programming<\/a>. The idea is that the optimal strategy when there are $t+1$ draws remaining depends on the optimal strategy when there are $t$ draws remaining. So if we work our way backwards from $t=0$, we can derive the strategy for any $t$.<\/p>\n