Past exam of the mathematics course of the University of Cambridge / 2022 / ii / Paper 1 / 31J / d / i / Solution

For one real coordinate, a union of $m$ intervals labels a fixed $n$-point sample by choosing at most $2m$ endpoints among the $n+1$ gaps, so the number of labelings is at most $(n+1{)}^{2m}$. Membership in a Cartesian product is the product of the $p$ coordinate-membership indicators. Applying part (c) repeatedly gives