Q21 Matemática  (KoMaL A Problems 2020)

Escolhemos uma permutação aleatória de $1,2,\dots ,n$ com distribuição uniforme. Prove que o valor esperado do comprimento da subsequência crescente mais longa na permutação é pelo menos $\sqrt{n}.$