Olympiad Maths Prep

Library / /32 of 45

Combinatorics Difficulty 6.5 National olympiad Prove it Ukraine

There are 100 cards, each with one of the numbers 11, 22, \ldots, 100100 written on it, such that each number appears on exactly one card. The cards are stacked in such a way that the numbers 11, 22, \ldots, 100100 are written from top to bottom in order. Petrik rearranges the cards according to the following rules. If, before his kk-th move, the numbers on the cards from top to bottom are arranged as follows: a1,a2,,ak1,ak,ak+1,,a100a_1, a_2, \ldots, a_{k-1}, a_k, a_{k+1}, \ldots, a_{100}, then after his move they are arranged as follows: ak,ak1,,a2,a1,ak+1,,a100a_k, a_{k-1}, \ldots, a_2, a_1, a_{k+1}, \ldots, a_{100} (so the order of the cards does not change when k=1k=1). Petryk takes turns making moves 11, 22, \ldots, 100100, and then makes moves 11, 22, \ldots, 100100 again, and so on. Will the initial arrangement of the cards with the numbers 11, 22, \ldots, 100100 from top to bottom necessarily be repeated after a finite number of moves?

Solution

Let us consider two moves: 2k12k-1 and 2k2k. Suppose that before the first of them there was a layout of cards a1,a2,,a2k1,a2k,a2k+1,,a100a_1, a_2, \ldots, a_{2k-1}, a_{2k}, a_{2k+1}, \ldots, a_{100}, then after two moves we will have the following changes:
a2k1,a2k2,,a1,a2k,a2k+1,,a100a2k,a1,a2,,a2k1,a2k+1,,a100. a_{2k-1}, a_{2k-2}, \dots, a_1, a_{2k}, a_{2k+1}, \dots, a_{100} \to a_{2k}, a_1, a_2, \dots, a_{2k-1}, a_{2k+1}, \dots, a_{100}.
Thus, after each pair of moves, the corresponding even number is moved to the first place. Therefore, after 100 moves, we will have such a layout of cards: 100100, 9898, 9696, \ldots, 44, 22, 11, 33, 55, \ldots, 9797, 9999. We will call this perturbation a *megamove*. We will call the initial position A0A_0, the position after the first megamove A1A_1, after the second A2A_2, and so on. It is not difficult to understand that if the position AmA_m arises from the position Am+1A_{m+1}, then vice versa, it cannot arise from any other position except for AmA_m. Therefore, let us consider the situation after a sufficiently large number of megamoves. They have to start repeating because there is a finite number of them possible. But if the position is repeated, then all previous ones coincide. Thus, the initial position had to repeat as well.

Looking for a route rather than an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.