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