= Solution
The best classical strategy avoids previously failed inputs: inspect a uniformly random permutation. Assume $1\le m\le N$ and let $K$ be the first marked position. For $K=k$, the first $k-1$ guesses must all fail and the next must succeed. Thus
$$
\boxed{\mathbb P(K=k)=
\left[\prod_{r=0}^{k-2}\frac{N-m-r}{N-r}\right]\frac{m}{N-k+1}
=\frac{\binom{N-k}{m-1}}{\binom Nm}.}
$$
The empty product covers $k=1$. The binomial form follows by choosing the $m$ marked positions uniformly: put one at $k$ and the remaining $m-1$ after it. This is the <first marked item in a random permutation> distribution.
The requested range is part of its support, but omits the last possible value $k=N-m+1$. All $N-m$ bad inputs can be encountered first, after which success is certain. The same formula includes that nonzero terminal probability; summing through this last value gives one. If $m=0$, the search never succeeds. If sampling were instead with replacement, its inferior repeated-guess strategy would have the geometric law $(1-m/N)^{k-1}m/N$ with no such finite endpoint.
Back to article page
