Question 63
There are $2^n$ soldiers standing in a line, where $n$ is a positive integer. The soldiers can rearrange themselves into a new line only in the following way: the soldiers standing at odd numbered positions move to the front of the row, keeping their positions with respect to each other, and the soldiers previously standing at even numbered positions move to the end of the row, keeping their positions with respect to each other. Prove that after $n$ rearrangements the soldiers stand in the same ordering as in the beginning.