Véletlenszerűen kiválasztjuk (egyenletes eloszlással) az $\mathrm{1,2,}\text{...}\mathrm{,}n$ számok egy permutációját. Bizonyítandó, hogy a permutációban a leghosszabb növő részsorozat hosszának várható értéke legalább $\sqrt[]{n}$.