Some books are placed on each other. Someone first, reverses the upper book. Then he reverses the $2$ upper books. Then he reverses the $3$ upper books and continues like this. After he reversed all the books, he starts this operation from the first. Prove that after finite number of movements, the books become exactly like their initial configuration.
Problem
Source:
Tags: induction, least common multiple, combinatorics proposed, combinatorics
peregrinefalcon88
17.08.2012 20:52
Firstly, we notice that we can ignore the orientation of any individual book because if the books return to their original positions in M moves, then another M moves will correct any orientation issues. Assume there are n books, we can show by induction that after 1 round (n moves) the sequence ${\{a_i\}_{i = 1}^n}$, $a_i = i$ which denotes the position of book i from the top, maps to the sequence $\{b_i\}_{i = 1}^n$ where $b_i = n+2-2i, 1 \le i \le \frac{n+1}{2}, b_i = 2i-n-1, \frac{n+2}{2} \le i \le n$. Now we can see that because the mapping is one-to-one, some number of cycles will form were position J will map back to itself in a minimum of K iterations of this mapping. It is also not difficult to see that any position P through which J iterates, also returns to its original position in a minimum of K iterations and that these cycles have no intersection with each other. It follows that if M is the least common multiple of the length of all cycles then M rounds will return all books to their original positions and 2M rounds will definetly return them to their original orientation as well.
Q.E.D.