On the table, there're $1000$ cards arranged on a circle. On each card, a positive integer was written so that all $1000$ 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 $k$, count the $k^{th}$ 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 $A$ such that, no matter what other card Vasya selects as first card, the one that left is always card $A$?
Problem
Source: All-Russian MO 2018 Grade 11 P5
Tags: combinatorics
28.04.2018 15:25
Yes: Consider the 1000 cards in the following clockwise order: $$1,\quad 1000!+1,\quad 2\cdot 1000!+1,\quad 3\cdot 1000!+1,\quad \dots\quad, \quad997\cdot 1000!+2,\quad 998\cdot 1000!+2,\quad A$$ This clearly works because if the card is $k\cdot 1000!+c$, we always move $c$ places forward no matter how many cards there are remaining in the circle
28.04.2018 18:24
Answer. It could. Official solution: Let us temporarily abandon the condition of sat down on the cards. Let $A$ and $B$ be two adjacent cards ($A$ le- after $B$ clockwise). Let's write on the card $A$ an arbitrary number, on the card $B$ - the number $2$, and on all the rest, cards are units. If Vasya removes the first one a card other than $A$, then he will take cards clockwise, "jump" through $A$ (since on $B$ the deuce is written). Hence, $A$ remains the last. It remains to make the numbers on the cards pairwise different. For this it is enough to add all the numbers on the cards different natural numbers, dividing by $1000!$. Indeed, if there are d cards left when the card $x$ is thrown out, the result of the process will not change if you add x to the card a number that is a multiple of d (Vasya will simply count a few extra complete circles). Hence, if the number on the card is added the number divisible by $1000!$, the result of the process will not change at any choice of the initially chosen card.
06.12.2019 00:22
998 numbers $\equiv 1 \pmod{lcm(1,2, ... , 1000)}$ and 2 numbers $\equiv 2 \pmod{lcm(1,2, ... 1000)}$.