Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Imperative programming / 1 / b

Take an integer pivot $0\le p\le N+1$. There are $p$ possible values in $[0,p)$ but only $k$ occurrences of such values in the whole array. When $k<p$, the pigeonhole principle givesRepeated values do not invalidate the argument: they can only reduce the number of distinct values represented by those $k$ occurrences. The other side might also contain a missing value.

There are $N+1-p$ candidate values in $[p,N+1)$ and exactly $N-k$ occurrences there. If $k\ge p$, thenThus the pigeonhole principle givesThis conclusion does not assert that every value on the lower side is present; duplicates may leave both sides deficient.