Past exam of the mathematics course of the University of Cambridge / 2022 / ii / Paper 1 / 31J / b

Choose $2m$ ordered points. Every subset of them has at most $m$ maximal consecutive runs, and those runs can be covered by at most $m$ closed intervals. Thus the points are shattered. On $2m+1$ ordered points, however, the alternating labelinghas $m+1$ separated positive runs and cannot be realized by a union of $m$ intervals. Therefore

These are indicators of affine half-spaces in ${\mathbb{R}}^p$. Adjoining a constant coordinate embeds their defining functions in the $(p+1)$-dimensional vector spaceThe VC dimension of a vector space bound therefore givesIn fact equality holds, but only the upper bound is required.