Voici mon raisonnement :

On note T(j,n,i,k) le nombre de jetons piochés en moyenne pour parvenir à en piocher j dans l'ordre croissant, à partir d'un sac en contenant n, sachant qu'un jeton faisant partie des i plus petits doit obligatoirement être remis dans le sac (jetons interdits pour cause de tirages antérieurs) et en suivant la tactique qui consiste à garder le premier jeton s'il fait partie des k plus petits (mais pas des jetons interdits), puis pour les jetons suivants à suivre la meilleure tactique possible.

On note T(j,n,i) le min des T(j,n,i,k)  (pour k variant entre i+1 et n-j+1)
et K(j,n,i) le k correspondant à ce minimum.

Notre but est de déterminer T(10,1000,0) ainsi que les différents K(j,990+j,i)

En raisonnant comme en #17, on établit que :

T(j,n,i,k) = 1 + (i+n-k)/n*T(j,n,i,k) + 1/n*Somme{pour ii=i+1 à k}de T(j-1,n-1,ii-1)

On en tire la relation de récurrence (sur j) suivante :

T(j,n,i,k) = 1/(k-i) * [n + Somme{pour ii=i+1 à k}de T(j-1,n-1,ii-1)]

Évidemment, T(0,n,i)=0, ce qui initialise la récurrence.

Voici un programme en Python (pas optimisé) :

nb_jetons_total = 10
nb_jetons_ordre = 4
T = [[0]*nb_jetons_total for j in range(nb_jetons_ordre+1)]
K = [[0]*nb_jetons_total for j in range(nb_jetons_ordre+1)]
for j in range(1,nb_jetons_ordre+1):    
    n = nb_jetons_total+j-nb_jetons_ordre
    for i in range(n-j+1):
        t_min = j*(2*n+1-j)/2+1        
        s = 0
        for k in range(i+1, n-j+2):
            s += T[j-1][k-1]
            t = (s+n)/(k-i)
            if t < t_min :
                t_min = t
                k_min = k
        T[j][i] = t_min
        K[j][i] = k_min+nb_jetons_ordre-j
print("Nombre de jetons piochés en moyenne :", T[nb_jetons_ordre][0])
print("Seuil n°1 :",K[nb_jetons_ordre][0])
k = K[nb_jetons_ordre][0]
for j in range(nb_jetons_ordre-1, 1, -1):
    print("Seuil n°",nb_jetons_ordre-j+1," en fonction du jeton n°",nb_jetons_ordre-j," (entre ",nb_jetons_ordre-j," et ",k,") : ",K[j][:k-nb_jetons_ordre+j+1],sep="")
    k = K[j][k+j-nb_jetons_ordre]

Une singularité à signaler: pour obtenir 1 jeton ordonné, il ne faut piocher qu'un jeton.
Pour 2 jetons ordonnés, il en faudra 2 de plus (avec qq chose après la virgule)
Pour 3 jetons ordonnés, il en faudra 3 de plus.
Pour n jetons ordonnés, il en faudra n de plus.

En réalité, ça dépasse légèrement, mais on n'est pas loin du n(n+1)/2.
Pour 10: 55. L'écart s'accroit mais très très lentement et en diminuant en pourcentage. 

Finalement, Gwen et Fix33 n'étaient pas tombés si loin du bon résultat !