= Solution
There are $N-k$ entries in $[p,N+1)$, which contains $N+1-p$ possible <integers>. If $k\geq p$, then $N-k\leq N-p<N+1-p$. Therefore \b[some value in $[p,N+1)$ is missing], again by the <pigeonhole principle>. This is an existence conclusion in the chosen interval, not a claim that all missing values lie there; both sides can contain missing values when duplicates occur.
If $p\leq0$, the upper side contains the whole permitted range and hence a missing value. If $p>N+1$, the condition $k\geq p$ is impossible. Outside the internal-pivot range this conclusion therefore supplies no improved localization.
Back to article page
