For a positive integer n(≥5), there are n white stones and n black stones (total 2n stones) lined up in a row. The first n stones from the left are white, and the next n stones are black. \Circle\Circle⋯\Circle⏟n\CIRCLE\CIRCLE⋯\CIRCLE⏟nYou can swap the stones by repeating the following operation. (Operation) Choose a positive integer k(≤2n−5), and swap k-th stone and (k+5)-th stone from the left. Find all positive integers n such that we can make first n stones to be black and the next n stones to be white in finite number of operations.
Problem
Source: KJMO 2023 P5
Tags: combinatorics
04.11.2023 19:54
Answer: All n which 5 divides. If 5|n, it's obvious that we can do this operation. Assume contrary. If n is not a multiple of n, let n=5k+r such that 4≥r≥1. If a white stone is in the (5m+s). place, then it will be in (5l+s). place for some l. Let's number the white stones from left to right as w1,...,wn and number the black stones from left to right as b1,...,bn for their initial positions. Let f(wi) be the place which the stone wi will be in the final position and s(wi) be the place which the stone wi is in at the initial position. We know that s(wi)≡f(wi)(mod5). There are k stones which hold s(wi)≡0(mod5). So there should be k stones which f(wi)≡0(mod5). There should be k numbers in the set (5k+r+1,5k+r+2,...,10k+2r) which is a multiple of 5. If r≥3, then the numbers are 5(k+1),5(k+2),...,5(2k),5(2k+1) so there would be k+1 numbers which gives us contradiction. So r≤2. There are k+1 stones which hold s(wi)≡1(mod5). But there are k stones which hold f(wi)≡1(mod5) which gives us contradiction.
18.06.2024 05:05
Nice solution using invariants