Games
(Belarus National Olympiad 2023 Grade 8 Day 1 P1, AoPS) A move on an unordered triple of numbers \((a,b,c)\) changes the triple to either \((a,b,2a+2b-c)\), \((a,2a+2c-b,c)\) or \((2b+2c-a,b,c)\). Can you perform a finite sequence of moves on the triple \((3,5,14)\) to get the triple \((3,13,6)\)?
Click here for the spoiler!
- Show that if a sequence of moves is performed on a triple \((a,b,c)\), then the resulting unordered triple is congruent to one of the triples \[ (a, b, - (a + b + c)), (a, - (a + b + c), c), (- (a + b + c), b, c), (a, b, c) \] modulo \(3\), that is, the residues of the entries of the resulting triple modulo \(3\) coincide with the residues of the entries of one of the above triples in some order.
(Belarus National Olympiad 2023 Grade 9 Day 1 P2, AoPS) A move on an unordered triple of numbers \((a,b,c)\) changes the triple to either \((a,b,2a+2b-c)\), \((a,2a+2c-b,c)\) or \((2b+2c-a,b,c)\). Can you perform a finite sequence of moves on the triple \((3,5,14)\) to get the triple \((9, 8, 11)\)?
Click here for the spoiler!
- Show that the mod \(4\) congruence class of the sum of the entries of such a triple remains invariant under the allowed moves if the sum of the entries of the initial triple is congruent to \(2\) modulo \(4\).
(Columbia National Olympiad 2025 P2, AoPS, proposed by Santiago Rodriguez) The numbers \(1, 2, \dots, 2025\) are written around a circle in some order. On each turn, Celeste chooses an integer \(1\leq n\leq 2025\). Then she selects the number \(n\) and the next \(n-1\) numbers following it in the clockwise direction and inverts their order on the circle. Prove that, after a finite amount of turns, Celeste can put the numbers on the circle in the order \(1,2,3,\dots, 2025\) in the clockwise direction, regardless of their original arrangement on the circle.
Click here for the spoiler!
-
Show that if the numbers \(2, 3, x\) appear consecutively in that order in the clockwise direction, then after a finite number of turns, they can be arranged in the order \(x, 2, 3\) in the clockwise direction, while keeping the order of the other numbers unchanged.
-
Show that if the numbers \(a, b\) appear consecutively in that order in the clockwise direction, then after a finite number of turns, they can be arranged in the order \(b, a\) in the clockwise direction, while keeping the order of the other numbers unchanged.
-
Using the above two results, prove that, given any arrangement of the numbers \(1, 2, \dots, 2025\) around the circle, after a finite number of turns, they can be arranged in the order \(1, 2, 3, \dots, 2025\) in this order in the clockwise direction.
Click here for the spoiler!
Let us prove a few claims about the operation.
Claim. If the numbers \(2, 3, x\) appear consecutively in that order in the clockwise direction, then after a finite number of turns, they can be arranged in the order \(x, 2, 3\) in the clockwise direction, while keeping the order of the other numbers unchanged.
Proof of the Claim. We can apply the operation with \(n = 2\) to the three numbers \(2, 3, x\) to get the arrangement \(3, 2, x\). Then we apply the operation with \(n = 3\) to the three numbers \(3, 2, x\) to get the arrangement \(x, 2, 3\). Note that the order of the other numbers is unchanged in both operations.
Claim. Let \(a, b, c\) be three distinct integers among \(1, 2, \dots, 2025\) different from \(2, 3\). If the numbers \(2, 3, a, b, c\) appear consecutively in that order in the clockwise direction, then after a finite number of turns, they can be arranged in the order \(2, 3, b, a, c\) in the clockwise direction, while keeping the order of the other numbers unchanged.
Proof of the Claim. We can apply the operation with \(n = 3\) to the arrangement \(2, 3, a, b, c\) to get the arrangement \(2, b, a, 3, c\). Then we apply the operation with \(n = 2\) to the arrangement \(2, b, a, 3, c\) three times to get the arrangement \(b, a, 3, 2, c\). Next, we apply the operation with \(n = 3\) to the arrangement \(b, a, 3, 2, c\) to get the arrangement \(b, a, c, 2, 3\). Note that the order of the other numbers is unchanged in all operations. Applying the above claim \(2020\) times, we get the arrangement \(2, 3, b, a, c\), without changing the order of the other numbers.
Claim. Let \(a, b, c\) be three distinct integers among \(1, 2, \dots, 2025\) different from \(2, 3\). If the numbers \(a, b, c\) appear consecutively in this order in the clockwise direction, then after a finite number of turns, they can be arranged in the order \(b, a, c\) in the clockwise direction, while keeping the order of the other numbers unchanged.
Proof of the Claim. Applying the operation with \(n = 2\) to \(2\) and the integer next to \(2\) in the clockwise direction, we obtain \(2, 3\) in this order in the clockwise direction. Then we can apply the previous claim to \(2, 3, a, b, c\) to get the arrangement \(2, 3, b, a, c\). Next, we apply the first claim to \(2, 3\) and the integer next to \(3\) in the clockwise direction to place \(2, 3\) in this order in the clockwise direction so that \(3\) is placed in the same position as before. Finally, we move \(2\) back to its original position by applying the operation with \(n = 2\) to \(2\) and the integer next to \(2\) in the clockwise direction. Note that the order of the other numbers is unchanged in all operations.
Now, given any arrangement of the numbers \(1, 2, \dots, 2025\) around the circle, we can arrange \(2, 3\) in this order in the clockwise direction. Next, applying the previous claim repeatedly, we obtain the arrangement \(1, 2, 3\) in this order in the clockwise direction. Finally, we can place the remaining numbers \(4, 5, \dots, 2025\) in the correct order by repeatedly applying the previous claim to adjacent triplets of numbers that are out of order.
Click here for the spoiler!
Let us prove the following claims.
Claim. If the numbers \(2, 3, x\) appear consecutively in that order in the clockwise direction, then after a finite number of turns, they can be arranged in the order \(x, 2, 3\) in the clockwise direction, while keeping the order of the other numbers unchanged.
Proof of the Claim. We can apply the operation with \(n = 2\) to the three numbers \(2, 3, x\) to get the arrangement \(3, 2, x\). Then we apply the operation with \(n = 3\) to the three numbers \(3, 2, x\) to get the arrangement \(x, 2, 3\). Note that the order of the other numbers is unchanged in both operations.
Claim. Let \(a, b\) be two distinct integers among \(1, 2, \dots, 2025\) different from \(2, 3\). If the numbers \(a, b\) appear consecutively in that order in the clockwise direction, then after a finite number of turns, they can be arranged in the order \(b, a\) in the clockwise direction, while keeping the order of the other numbers unchanged.
Proof of the Claim. Applying the operation with \(n = 2\) to \(2\) and the integer next to \(2\) in the clockwise direction, we can place \(2, 3\) in this order in the clockwise direction. Then applying the prior claim to \(2, 3\) and the integer next to \(3\) in the clockwise direction, we can obtain the arrangement \(2, 3, a\) in this order in the clockwise direction. Next, applying the operation with \(n = 3\) to the arrangement \(2, 3, a, b\) gives the arrangement \(2, b, a, 3\). Then we apply the operation with \(n = 2\) to the arrangement \(2, b, a, 3\) two times to get the arrangement \(b, a, 2, 3\). Applying the prior claim to \(2, 3\) and the integer next to \(3\) in the clockwise direction, we can place \(2, 3\) in this order in the clockwise direction so that \(3\) is placed in the same position as before. Finally, we move \(2\) back to its original position by applying the operation with \(n = 2\) to \(2\) and the integer next to \(2\) in the clockwise direction. Note that the order of the other numbers is unchanged in all operations.
Now, given any arrangement of the numbers \(1, 2, \dots, 2025\) around the circle, we can arrange \(2, 3\) in this order in the clockwise direction. Next, applying the previous claim a finite number of times, to integers lying between \(3\) and \(4\) in the clockwise direction, we can obtain the arrangement \(2, 3, 4\) in this order in the clockwise direction. Next, after obtaining the arrangement \(2, 3, 4, \dots, k\) in this order in the clockwise direction, for some \(4 \leq k < 2025\), we can apply the previous claim a finite number of times to integers lying between \(k\) and \(k + 1\) in the clockwise direction to get the arrangement \(2, 3, 4, \dots, k, k + 1\) in this order in the clockwise direction. It follows that we can obtain the arrangement \(2, 3, 4, \dots, 2025\) in this order in the clockwise direction. This gives the desired arrangement \(1, 2, 3, \dots, 2025\) in this order in the clockwise direction.
(Kosovo National Olympiad 2023 Grade 11 P1, AoPS) In three different piles, there are \(51\), \(49\) and \(5\) stones, respectively. You can combine two piles in a larger pile or you can separate a pile that contains an even amount of stones into two equal piles. Is it possible that after some turns, we can separate the stones into \(105\) piles with \(1\) stone on each pile?
Click here for the spoiler!
- Show that the greatest common divisor of the numbers of stones of the piles is an odd integer larger than \(1\).
- Show that it is impossible to separate the stones into \(105\) piles with \(1\) stone on each pile.
Click here for the spoiler!
Note that if the greatest common divisor of the numbers of stones of the piles before some turn is an odd integer \(d\), then \(d\) divides the number of stones in each pile after that turn. Since \(5, 49, 51\) are all odd, it follows that during the first turn two piles are to be combined. Hence, the numbers of stones in the piles after the first turn are equal to \(5, 100\), or to \(49, 56\), or to \(51, 54\). This shows that the greatest common divisor of the numbers of stones of the piles is an odd integer larger than \(1\). Consequently, it is impossible to separate the stones into \(105\) piles with \(1\) stone on each pile after some turns.
Lecture notes for Math Olympiad (IOQM, RMO, INMO)
Click on the icons below to download.
Topics Links Algebra Combinatorics Geometry Number Theory INMO Training Camp IMO Training Camp MOPSS Simon Marais Mathematics Competition Resources