On the table, there're cards arranged on a circle. On each card, a positive integer was written so that all numbers are distinct. First, Vasya selects one of the card, remove it from the circle, and do the following operation: If on the last card taken out was written positive integer , count the clockwise card not removed, from that position, then remove it and repeat the operation. This continues until only one card left on the table. Is it possible that, initially, there's a card such that, no matter what other card Vasya selects as first card, the one that left is always card ?
Problem 1328
Official solution
1. Initial Setup: Consider a circle with 1000 cards, each labeled with a distinct positive integer. We need to determine if there exists a card such that no matter which card Vasya starts with, the last remaining card is always .
2. Simplified Case: Let's first simplify the problem by temporarily ignoring the distinctness condition. Assume we have two adjacent cards and , where is immediately clockwise from . Assign the number 1 to all cards except , which is assigned the number 2.
3. Operation Analysis:
- If Vasya removes any card other than first, he will continue removing cards in a clockwise manner.
- When he reaches , the number 2 on will cause him to skip and continue removing the next card.
- This skipping ensures that is never removed until all other cards are removed.
4. Ensuring Distinct Numbers: To satisfy the condition that all numbers on the cards are distinct, we can add distinct multiples of to each card. This ensures that:
- The relative order of removal remains unchanged because adding multiples of does not affect the counting process modulo 1000.
- Each card will have a unique number since is a very large number, and adding distinct multiples of it will ensure distinctness.
5. Conclusion: By assigning numbers in this manner, we ensure that card will always be the last remaining card, regardless of which card Vasya starts with.