= Solution
With one marked input, after $r$ distinct failed guesses it is uniformly distributed among the $N-r$ untested inputs. Therefore the conditional chance of success on the next guess is $1/(N-r)$. One further failure raises it by
$$
\boxed{\frac1{N-r-1}-\frac1{N-r}=\frac1{(N-r-1)(N-r)},\quad 0\le r\le N-2,}
$$
or by a multiplicative factor $(N-r)/(N-r-1)$. There is a different unconditional statement: the marked position is uniform, so $\mathbb P(K=k)=1/N$ and $\mathbb P(K\le k)=k/N$. Thus each additional distinct guess increases cumulative success by $1/N$, even though the conditional next-guess probability increases after each failure. These distinguish the two possible meanings of a probability boost.
Back to article page
