Maths Olympiad Prep

Library / /262 of 520

Combinatorics Difficulty 6.9 National olympiad Prove it

Write the natural numbers from left to right in ascending order. Every minute, we perform an operation. After mm minutes, we divide the entire available series into consecutive blocks of mm numbers. We leave the first block unchanged and in each of the other blocks we move all the numbers except the first one one place to the left, and move the first one to the end of the block. Prove that throughout the process, each natural number will only move a finite number of times.

Solution

1. Assume the contrary: Suppose there exists a natural number that moves infinitely many times. Let this number be in position p p .

2. Operation description: After m m minutes, the series is divided into blocks of m m numbers. The first block remains unchanged. In each subsequent block, the first number moves to the end, and all other numbers shift one place to the left.

3. Position update rule: If the number is in position p p at minute m m :
- If mp m \mid p , then p p is replaced by p+m1 p + m - 1 .
- Otherwise, p p is replaced by p1 p - 1 .

4. Infinite movement implication: Since the number moves infinitely often, it can never reach p=0 p = 0 . Therefore, it must move to the right infinitely often.

5. Movement analysis: Suppose at minute N+1 N+1 , the number moves forward from position p=k(N+1) p = k(N+1) to p=(k+1)(N+1)1 p = (k+1)(N+1) - 1 .

6. Non-increasing ratio claim: The ratio k k is non-increasing. If the next rightward move occurs at minute N++1 N + \ell + 1 , then:
N++1(k+1)(N+1)1 N + \ell + 1 \mid (k+1)(N+1) - \ell - 1
This ratio is at most k k and exactly k k only when (k+1)=N \ell \cdot (k+1) = N .

7. **Stabilization of k k **: Since k k cannot become zero, it must stabilize at some value K K .

8. **Largest integer z z **: Let z z be the largest nonnegative integer such that (K+1)zN (K+1)^z \mid N .

9. **Sequence of \ell **: The first value of \ell is Nk+1 \frac{N}{k+1} . The next value is:
N+k+1=Nk+1+N(k+1)2 \frac{N + \ell}{k+1} = \frac{N}{k+1} + \frac{N}{(k+1)^2}
and so on.

10. Integer condition: These values cannot be integers after z z steps, causing k k to decrease.

11. Conclusion: Eventually, k k becomes smaller than one, at which point the number stops moving.

Therefore, each natural number will only move a finite number of times.

\blacksquare

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.