I don't think I'll explain it very well, and I'm not sure it's correct, but I'll try . Let $t$ be the card on position $n$ at the beginning. Until we reach the situation when we have to move the card $n$, the game goes on just as if it were a game with cards $1,2,\ldots,n-1$ and positions $0,2,\ldots,n-1$ (i.e. until we have to move card $n$, we have no idea that it's card $n$ and not card $t$). Since such a game can have at most $2^{n-1}-1$ steps (from th induction hypothesis), and when we meet $n$ we need one more move to put it in its place, on position $n$, it means that in at most $2^{n-1}$ moves card $n$ is in its place. We repeat the reasoning: after that, we need at most $2^{n-2}$ moves to put card $n-1$ in its place, and so on, until $2,3,\ldots,n$ are in their places, and we need at most $1$ move to put card $1$ in its place (and then $0$ will be in its place automatically). In total, we need at most $1+2^1+2^2+\ldots+2^{n-1}=2^n-1$ moves. As for the arrangement, using the argument above and induction, we get that it must be $1,2,\ldots,n,0$.

yes! the secound part is an induction.... Try the following for the first part: To each configuration asign an n tuple $a_2,a_3,...a_{n+1}$ such that $a_i=1$ iff $i$ is on the right place, and $0$ otherwise. Prove no 2 ntuples repeat during the proccess, and thats it.

Pascual2005 wrote: Try the following for the first part: To each configuration asign an n tuple $a_2,a_3,...a_{n+1}$ such that $a_i=1$ iff $i$ is on the right place, and $0$ otherwise. Prove no 2 ntuples repeat during the proccess, and thats it. First of all, one thing that confuses me is that we have no $n+1$, so what is $a_{n+1}$? Why did you number the sequence from $2$ to $n+1$?

well actually use the nuemration from $1$ to $n$, exclude the card with the $0$ because it is very predictible its behavior...then prove no 2 n tuples repeat.

You know, I did try some stuff with such binary representations (that $2^n$ suggests such an approach), but somehow, I didn't see this . it looks like if you reverse the binary vector you have described, you get the binary representations of a the elements in a strictly increasing sequence. Thanks! P.S. I still think my solution is also correct though

It is I was just proposing another aproach..

Solution by seshadri: if $ 0$ appears in position $ 0$, then effectively the procedure works on the permutation from $ 1$ to $ n$ and so we can induct, so WLOG $ \pi(0)\neq 0$. it suffices to show that if $ n$ is in position $ k$, then the number of steps it takes for $ n$ to move to position $ n$ is atmost $ 2^{k}$. (thus when we induct we do so on $ n + k$). Suppose $ n$ is in position $ k$ and we are done in all smaller cases. if in fewer than $ 2^{k - 1}$ steps $ n$ moves forward, then we are done by induction. If this is not the case then in $ 2^{k - 1}$ steps all changes have occured only in positions $ 0$ through $ k - 1$. hence it follows that $ \pi(0),\pi(1),\ldots,\pi(k - 1)\in\{0,1,\ldots,k - 1\}$ and hence $ \pi|_{\{0,1,\ldots,k - 1\}}\in \mathcal{S}_k$. By induction we know that these can be sorted in atmost $ 2^{k} - 1$ steps and so $ n$ can be transferred to position $ n$ in atmost $ 2^k$ steps and that completes the induction. clearly if the number of steps is to be maximum then again we can argue inductively that the corresponding permutation has to be $ 12\cdots(n - 1)n1$.