Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
 Already signed up? New to KöMaL?

# Problem A. 759. (October 2019)

A. 759. We choose a random permutation of numbers $\displaystyle 1, 2,\dots, n$ with uniform distribution. Prove that the expected value of the length of the longest increasing subsequence in the permutation is at least $\displaystyle \sqrt{n}\,$.

Proposed by László Surányi, Budapest

(7 pont)

Deadline expired on November 11, 2019.

### Statistics:

 10 students sent a solution. 7 points: Bán-Szabó Áron, Beke Csongor, Füredi Erik Benjámin, Gyimesi Péter, Pooya Esmaeil Akhoondy, Stomfai Gergely, Szente Péter, Várkonyi Zsombor, Weisz Máté. 6 points: Hegedűs Dániel.

Problems in Mathematics of KöMaL, October 2019