This is as Erdős posed the problem in [Er71], which is rather ambiguous. Discussion between several users in the comments section has led to the following precise possible question, as posed by van Doorn:

What is the largest constant $c$ such that, for all sequences of $n$ real numbers $x_1,\ldots,x_n$,\[\max\left(\sum x_{i_r}\right)> (c-o(1))\frac{1}{\sqrt{n}}\sum x_i\](where again the maximum is taken over all monotonic subsequences)? A construction of Cambie in the comments shows that $c\leq 1$. Hanani [Ha57] showed that every sequence is the disjoint union of at most $(\sqrt{2}+o(1))\sqrt{n}$ many monotonic subsequences, whence $c\geq 1/\sqrt{2}$.

Cambie makes the stronger conjecture that if $x_1,\ldots,x_{k^2}$ are distinct positive real numbers with $\sum x_i=1$ then there is always a monotonic subsequence with sum at least $1/k$. This is a weighted-form of the Erdős-Szekeres theorem, and is also mentioned (as an open question) in a survey on the latter by Steele [St95].

This stronger conjecture appears to have been first proved by Tidor, Wang, and Yang [TWY16], and is also implicit in work of Wagner [Wa17]. A proof was given and formalised by Aristotle (see the comments), with an alternative proof provided by Chan. In particular, this shows that $c=1$.

View the LaTeX source

This page was last edited 08 December 2025. View history