= Solution
Given $X_n=k$, the next child takes a fresh uniform choice from $1,\ldots,k$, making $X_{n+1}$ uniform on $0,\ldots,k-1$. At zero the count stays zero. This conditional law depends only on the current count, so $X_n$ is a <Markov chain>.
The amounts taken do not generally retain that state information. For $N\geq3$, compare two positive-<probability> histories with the same current value $Y_2=1$: if $Y_1=N-2$, exactly one sticker remains and $Y_3=1$; if $Y_1=N-1$, none remains and $Y_3=0$. Thus the next amount depends on earlier history even after conditioning on the current amount, violating the <Markov property>.
The non-Markov assertion needs this nondegenerate range of $N$. With $N=1$ the amount process is trivial; for $N=2$ it is also Markov if time-inhomogeneous transitions are permitted. The history counterexample establishes the intended failure for every $N\geq3$.
Back to article page
