Past exam of the mathematics course of the University of Cambridge / 2023 / iii / Paper 208 / 4 / c / Solution

Let $Z_i$ be the longest increasing subsequence length after deleting coordinate $i$. Then $0\le Z-Z_i\le 1$. Choose one longest increasing subsequence $I$ of length $Z$. If deleting $i$ reduces the optimum, then $i$ must belong to $I$; consequently at most $Z$ coordinates can satisfy $Z-Z_i=1$. Henceso $Z$ is a weakly self-bounding function. The variance bound for a weakly self-bounding function gives