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

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.