# How much can you pull out of a hat? This week’s Riddler Classic is a strategy game about maximizing payout. What is the optimal strategy?

You 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.

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. If you play this game perfectly — that is, to maximize the total amount of money you’ll receive after all 100 rounds — how much money would you expect to receive on average? My solution: [Show Solution] ## One thought on “How much can you pull out of a hat?” 1. Guy Moore says: You can make a pretty good estimate of the width and central value of the probability distribution in log(n) which you find. Note that, except for the first few draws, n is generally large. In the approximation that it’s large, the k-value which is drawn varies continuously from 0 to n, or (k/n) ranges from 0 to 1. The increase in ln(n) is ln(1+k/n). The mean and variance are: (LaTeX notation) $$\langle \Delta \ln(n) \rangle = \int_1^2 \ln(y) dy = 2 \ln(2) – 1$$ and $$\Delta \sigma^2 = \int_1^2 ( \ln(y) + 1 – 2 \ln(2) )^2 dy = 1 – 2 (\ln(2))^2$$ which are approximately .3863 and .0391 respectively. The distribution of$\ln(n)\$ is approximately Gaussian by the central limit theorem,
with a squared width of about 98*.0391.
Actually one should be a little more careful —
the final two draws have a fairly large variance as well, which should be computed and included separately.