= Solution
Given $X_n=k>0$, the number remaining next time is uniform on $\{0,\ldots,k-1\}$ and is independent of earlier choices; given $X_n=0$, the next state is $0$. Thus the conditional law of $X_{n+1}$ depends only on $X_n$, which is the <Markov property>.
By contrast, observing only the last number removed generally loses information about the remaining stock. For $N\geq3$, compare the two positive-<probability> histories
$$
(Y_1,Y_2)=(1,1),\qquad (Y_1,Y_2)=(N-1,1).
$$
Both have $Y_2=1$, but the first leaves $N-2>0$ stickers, so $P(Y_3>0\mid Y_1=1,Y_2=1)=1$, whereas the second leaves none, so $P(Y_3>0\mid Y_1=N-1,Y_2=1)=0$. Hence $(Y_n)$ fails the <Markov property>.
The qualification $N\geq3$ is necessary if a <Markov chain> is allowed to have time-dependent transitions. For $N=1$, the removal sequence is the deterministic, time-homogeneous <Markov chain> $1,0,0,\ldots$. For $N=2$, it is a time-inhomogeneous <Markov chain>, although it is not time-homogeneous on its observed removal states: a removal of $1$ at the first step forces another removal of $1$, whereas a removal of $1$ at the second step forces $0$ next. The blanket non-Markov claim should therefore be understood in the generic, nondegenerate setting.
Back to article page
