Problem 1026 on the Erdős problem web site recently got solved through an interesting combination of existing literature, online collaboration, and AI tools. The purpose of this blog post is to try to tell the story of this collaboration, and also to supply a complete proof.
The original problem of Erdős, posed in 1975, is rather ambiguous. Erdős starts by recalling his famous theorem with Szekeres that says that given a sequence of distinct real numbers, one can find a subsequence of length which is either increasing or decreasing; and that one cannot improve the to , by considering for instance a sequence of blocks of length , with the numbers in each block decreasing, but the blocks themselves increasing. He also noted a result of Hanani that every sequence of length can be decomposed into the union of monotone sequences. He then wrote “As far as I know the following question is not yet settled. Let be a sequence of distinct numbers, determine
where the maximum is to be taken over all monotonic sequences“.
This problem was added to the Erdős problem site on September 12, 2025, with a note that the problem was rather ambiguous. For any fixed , this is an explicit piecewise linear function of the variables that could be computed by a simple brute force algorithm, but Erdős was presumably seeking optimal bounds for this quantity under some natural constraint on the . The day the problem was posted, Desmond Weisenberg proposed studying the quantity , defined as the largest constant such that
for all choices of (distinct) real numbers. Desmond noted that for this formulation one could assume without loss of generality that thewere positive, since deleting negative or vanishingdoes not decrease the left-hand side and does not increase the right-hand side. By a limiting argument one could also allow collisions between the, so long as one interpreted monotonicity in the weak sense.
Though not stated on the web site, one can formulate this problem in game theoretic terms. Suppose that Alice has a stack of coins for some large . She divides the coins into piles of consisting of coins each, so that . She then passes the piles to Bob, who is allowed to select a monotone subsequence of the piles (in the weak sense) and keep all the coins in those piles. What is the largest fraction of the coins that Bob can guarantee to keep, regardless of how Alice divides up the coins? (One can work with either a discrete version of this problem where the are integers, or a continuous one where the coins can be split fractionally, but in the limit the problems can easily be seen to be equivalent.)
AI-generated images continue to be problematic for a number of reasons, but here is one such image that somewhat manages at least to convey the idea of the game:
For small , one can work out by hand. For , clearly : Alice has to put all the coins into one pile, which Bob simply takes. Similarly : regardless of how Alice divides the coins into two piles, the piles will either be increasing or decreasing, so in either case Bob can take both. The first interesting case is . Bob can again always take the two largest piles, guaranteeing himself of the coins. On the other hand, if Alice almost divides the coins evenly, for instance into piles for some small , then Bob cannot take all three piles as they are non-monotone, and so can only take two of them, allowing Alice to limit the payout fraction to be arbitrarily close to . So we conclude that .
An hour after Desmond’s comment, Stijn Cambie noted (though not in the language I used above) that a similar construction to the one above, in which Alice divides the coins into pairs that are almost even, in such a way that the longest monotone sequence is of length , gives the upper bound . It is also easy to see that is a non-increasing function of , so this gives a general bound . Less than an hour after that, Wouter van Doorn noted that the Hanani result mentioned above gives the lower bound , and posed the problem of determining the asymptotic limit of as , given that this was now known to range between and . This version was accepted by Thomas Bloom, the moderator of the Erdős problem site, as a valid interpretation of the original problem.
The next day, Stijn computed the first few values of exactly:
... continue reading