You have 20 spaces, which you want to fill with numbers, in order. You will be given 20 random numbers between 0 and 999 (inclusive), each of which you must place into a space as soon as you see it. If you can place all 20 while keeping them in order, you win.

What’s your best strategy? How likely are you to win?

I’ve done some analysis, which I’ve put below the line because it might constitute a spoiler.

For me, the trick to analysing this game is to realise that every move splits a group of spaces into two parts, one or both of which may be empty.

The probability of being able to successfully fill those parts is the product of two factors:

  • the probability that the remaining numbers will fall into the two parts, regardless of order; and
  • the probability that you can fill a part of that size and with that many spaces.

Typically, it’s easier to fill two parts if they have roughly even-sized spaces. However, the number of spaces available also affects the analysis.

The probability of winning the two-space game is around 75% – if you start with a middling number, you have a 50-50 chance of placing the other correctly, if you start with an extreme number, you are almost certain to place the next correctly, and it averages out to three-quarters1.

For a harder example, in the three-space game, your first move splits the spaces either into a part with two spaces and a part with none, or two parts, each with one space.

If your first number is $x$, it splits the 1000 numbers into parts of size $x$ and size $1001-x$. 2 Without loss of generality, I’ll assume that $x > 500$. We could sensibly:

  • Put $x$ in the middle slot and hope that the remaining two numbers fall either side of it; or
  • Put $x$ in the high slot and hope that neither remaining number is larger.

In the first case, the probability of the numbers splitting correctly is $\frac{2x(1001-x)}{1000^2}$, via the binomial distribution; if they split correctly, we win automatically.

In the second, the probability of the numbers splitting correctly is $\frac{x^2}{1000^2}$, also via binomial, but we only have about a 75% chance of correctly placing the remaining numbers.

There’s a crossover point where the two probabilities are the same: $2x(1001-x) = \frac{3}{4}x^2$ when $x=728$. If $x$ is larger than this, it’s best to put $x$ in the high slot; smaller (but bigger than the corresponding low-side $x$ of 273), it’s best to put $x$ in the middle. For 728 itself, it doesn’t matter.

If you sum all of the possibilities, you find that this strategy wins about 52% of the time.

I wrote code to analyse the 20-number case, because while I have some spare time to play around with these things, it’s not infinite. It’s on github. Play if you like.

The upshot is, you should expect to win the 20-number challenge about once every 9000 attempts, with perfect play. Good luck!

  1. It turns out to be linear, so this is legitimate analysis rather than ball-parking. ↩

  2. The extra 1 comes because if you drew another $x$, it could reasonably go in either space without being out of order. ↩