Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Imperative programming resit / 2 / b / i

For an integer pivot $0\le p\le N+1$, exactly $k$ entries lie in $[0,p)$. That interval contains $p$ possible integers. If $k<p$, the pigeonhole principle implies that some value in $[0,p)$ is missing. Counting occurrences rather than distinct entries only strengthens this argument: $k$ occurrences cannot cover more than $k$ distinct values.

For completeness, if $p>N+1$ the lower side contains the entire permitted value range, which already has a missing value. If $p\le 0$, the condition $k<p$ is impossible. Thus the general conclusion is a missing permitted value below $p$; an internal pivot gives useful localization.