Write the natural numbers from left to right in ascending order. Every minute, we perform an operation. After minutes, we divide the entire available series into consecutive blocks of 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 .
2. Operation description: After minutes, the series is divided into blocks of 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 at minute :
- If , then is replaced by .
- Otherwise, is replaced by .
4. Infinite movement implication: Since the number moves infinitely often, it can never reach . Therefore, it must move to the right infinitely often.
5. Movement analysis: Suppose at minute , the number moves forward from position to .
6. Non-increasing ratio claim: The ratio is non-increasing. If the next rightward move occurs at minute , then:
This ratio is at most and exactly only when .
7. **Stabilization of **: Since cannot become zero, it must stabilize at some value .
8. **Largest integer **: Let be the largest nonnegative integer such that .
9. **Sequence of **: The first value of is . The next value is:
and so on.
10. Integer condition: These values cannot be integers after steps, causing to decrease.
11. Conclusion: Eventually, becomes smaller than one, at which point the number stops moving.
Therefore, each natural number will only move a finite number of times.