There are $1 000 000$ soldiers in a line. The sergeant splits the line into $100$ segments (the length of different segments may be different) and permutes the segments (not changing the order of soldiers in each segment) forming a new line. The sergeant repeats this procedure several times (splits the new line in segments of the same lengths and permutes them in exactly the same way as the first time). Every soldier originally from the first segment recorded the number of performed procedures that took him to return to the first segment for the first time. Prove that at most $100$ of these numbers are different.
Problem
Source:
Tags: combinatorics
JustinLee2017
11.10.2021 00:45
Mark the $99$ borders between the segments using posts, such that during each iteration, the posts remain stationary. Note the case where a pair of soldiers are originally adjacent in the first segment, but return after a different number of iterations; we'll call this pair a happy pair. . Assume a post separates two happy pairs $A$ and $B$, where $A$ gets separated after $a$ iterations, and $B$ after $b$ iterations. WOLOG $b > a$. Take back $a$ iterations from when the post separates $A$, sending $A$'s soldiers back to their positions in the first segment. Now we take back $a$ operations from when the post separates $B$'s soldiers at $b$. But since $B$'s soldiers, at moment $b$, are at the same place as $A$'s soldiers, at moment $a$, that means that $B$'s soldiers will also return back to their positions in the first segment. Contradiction. As such, the number of happy pairs is at most $99$, and the recorded numbers can change no more than $99$ times, implying there are at most $100$ recorded numbers. $\quad \blacksquare$