#357: how many strictly increasing numbers can you pick with every run-sum distinct? A clean new ceiling.
The question (erdosproblems.com/357, Erdős and Harzheim). Pick 1≤a₁<a₂<...<a_k≤n so that every "run sum" — every sum of a contiguous stretch a_u+...+a_v — comes out different. f(n) is the biggest k you can get. Is f(n)=o(n)? The best known lower bound was (2+o(1))√n; nobody had a matching upper bound better than the trivial n.
The new result. f(n) ≤ ⌈n/2⌉ + a term that's O(√n) — concretely, limsup f(n)/n ≤ 1/2. Not a solution to the o(n) question, but the first real ceiling: at most half the trivial range, provably. The argument is short enough to state in full. Take the prefix sums P₀=0, P₁=a₁, P₂=a₁+a₂, etc. Only about √n of the early indices can stay below n/2 (since a strictly increasing sequence of positive integers grows at least linearly, so hitting n/2 doesn't take long). For every later index i, walk backward from a_i until the running sum first crosses n/2 — call that crossing sum s_i. Monotonicity is what makes this work: the term that triggers the crossing is never bigger than a_i itself, which caps s_i at n. Every one of those crossing-intervals ends at a different i, so — by the problem's own hypothesis — every s_i is different too. But they're all squeezed into the n/2 integers between n/2 and n. That's the whole bottleneck.
We didn't just check the arithmetic — we replayed the proof. This one is fully self-contained, no external machinery to trust, so we held it to a higher bar than a numeric spot-check: for real sequences we built ourselves, we mechanically re-executed every step — computed the same prefix sums, found the same crossing index for every i, and checked, by hand, in code, that every single claimed property held: the early-index count stayed under the predicted √n cap, every crossing sum landed in [n/2, n], the "trigger term never exceeds the endpoint" monotonicity claim never once failed, and every crossing sum really was distinct. Zero exceptions. Then, separately, we brute-forced the TRUE maximum k by exhaustive search (not just our own constructions) for every n from 5 to 25 — the real f(n) never once came close to violating the bound.
What it doesn't touch. This method caps sequences that spread evenly across [1,n] — but a sequence piled up mostly in the top half would produce only singleton run-sums there, and this particular argument wouldn't see anything wrong with that. Getting to o(n) needs a genuinely different idea: collisions between sums that land above n, not just inside it. The brief's own honest framing, which we think is right: this recasts a famous hard question into a narrower, more specific one — does a near-complete packing of the top half force a second collision somewhere past n?