Best possible approach for solving a random number list sorting challenge

Question

My son recently came up with a challenge. The idea is you will be initially given a list with 20 empty slots in it. You will then roll a random number generator that will give you a number between 1 and 1000 inclusive and you have to put the number into an empty slot in the list while endeavouring to keep the list sorted. Repeat this random number generation 20 times (or until you hit a point where you can't put the most recently generated random number into an empty slot without breaking the list ordering). "Success" means placing all 20 numbers in the list and the list being correctly sorted.

I wrote a quick Python program to play this as a game and found it very difficult to beat. So then I wrote a solver which does the best it can to place numbers "sensibly" (I can share the algorithm I used for choosing a slot if anyone is interested) and found that it typically only succeeds in filling the list 1 or 2 times in 100,000 trials (0.001 or 0.002% of the time). My intuition says it should be possible to write a solver that is a LOT better than that.

My question is: is there a way to calculate the expected success rate of the idealised solver?

Answer 1

The following bit of Python code tells me to expect an ideal winrate of at most 0.0142%:

from math import comb
fill = [[] for i in range(21)]
fill[0] = [1]*1001
for n in range(1,21):
    for d in range(1000):
        fill[n].append(sum(max(fill[i][k]*fill[n-1-i][d-k]*comb(n-1,i) for i in range(n)) for k in range(d+1)))
print(fill[-1][-1]/10**60)

In the program, n is the number of empty slots in an interval, and d is the difference between the endpoints of an interval. For each n from 1 to 20 and d from 0 to 999, we do the following:

• Simulate a draw of each of the d+1 numbers that can be placed within the interval. Call the currently-drawn number k.
• Each of the n slots that k could be placed in splits the interval into two new intervals. Check fill for the number of ways that each interval could be filled, and multiply those together. Since the sequences that fill the subintervals can be interleaved, and the value of k lets you determine which sequence you've drawn from*, multiply by the number of ways these sequences can be combined.
• The greatest of these n products gives the number of winning sequences under the ideal placement of k. Add up the total number of sequences for all k, and place the sum into the corresponding place in fill.
• Once all calculations are finished, fill[20][999] will give you the number of winning sequences for the original problem, and this can be divided by the $1000^{20}$ possible draws to obtain the final probability.

*This overcounts the cases where k is drawn multiple times and can be placed in either subinterval. Duplicates occur in roughly 17.5% of draws, so some further analysis is needed.