You are given $2^n$ numbers, in one step you move the numbers in odd positions to the beginning of the list and the numbers in even positions to the end of the list, keeping the initial order among them. Prove that after $n$ such steps, you will get the initial list.
How do I do this? Someone told me to look at positions of these numbers in binary, but I still don't understand how that helps yet...
Index the $2^n$ list positions of elements as $\underbrace{00\ldots00}_n, \underbrace{00\ldots01}_n, \ldots,\underbrace{11\ldots10}_n, \underbrace{11\ldots11}_n$. (These are indices given to the $2^n$ positions, not to elements that may move around the list)
In each reposition / shuffle step, for the element at position $b_{n-1}b_{n-2}\ldots b_1b_0$, its destination position is at $b_0b_{n-1}\ldots b_2b_1$, i.e. a cyclic right shift of bits. This is because $b_0$ determines whether the destination is in the beginning ($0$) or ending ($1$) half, and $b_{n-1}b_{n-2}\ldots b_1$ determines the position inside that half.
After $n$ cyclic right shifts of bits, the element initially at $b_{n-1}b_{n-2}\ldots b_1b_0$ moves through positions $$\begin{align*} b_{n-1}b_{n-2}\ldots b_1b_0 &\mapsto b_0b_{n-1}\ldots b_2b_1\\ &\mapsto b_1b_0\ldots b_3b_2\\ &\vdots\\ &\mapsto b_{n-2}b_{n-3}\ldots b_0b_{n-1}\\ &\mapsto b_{n-1}b_{n-2}\ldots b_1b_0\\ \end{align*}$$
and goes back to its initial position.