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

Leave a Reply

Your email address will not be published. Required fields are marked *