Maths Olympiad Prep

Library / /2 of 4

Combinatorics Difficulty 6.7 National Olympiad Prove it Romania

Let nn and kk be natural numbers, where 1k<n1 \le k < n. At each vertex of a regular polygon with nn sides, either 11 or 1-1 is written. At each step, we choose kk consecutive vertices and change their signs. Is it possible, starting from any configuration and performing this transformation multiple times, to obtain any other configuration?

Solution

Let d=(n,k)d = (n, k). If d>1d > 1 and n=dmn = dm, k=dlk = dl, then by performing the global move
e1e2ekek+1e2k+1em(kk+1)e2ek+2e2k+2em(kk+2) e_1 e_2 \dots e_k e_{k+1} e_{2k+1} \dots e_{m(k-k+1)} e_{2e_{k+2}} e_{2k+2} \dots e_{m(k-k+2)}
we obtain the initial configuration. The same configuration can also be obtained by performing the null move. Thus, in this case, we have two different global moves that produce the same configuration, so the answer is negative.

If d=1d = 1 and kk is even, then the global move e1e2ene_1 e_2 \dots e_n changes each vertex an even number of times, so it has the same effect as the null move. Therefore, in this case, the answer is negative.

Finally, if d=1d = 1 and kk is odd, we will show that the answer is affirmative. For this, it suffices to show that from the configuration C=1,1,1,,1C = 1, 1, 1, \dots, 1 we can obtain the configuration C=1,1,1,,1C' = -1, 1, 1, \dots, 1. Since (2n,k)=1(2n, k) = 1, there exist natural numbers mm and ll such that 2nm+1=kl2nm + 1 = kl. The global move e1e2ek+1e2k+1e(l1)(k+1)e_1 e_2 \dots e_{k+1} e_{2k+1} \dots e_{(l-1)(k+1)} changes each vertex, except the first one, 2m2m times, and the first vertex is changed 2m+12m + 1 times, thus transforming CC into CC'.

In conclusion, the answer is affirmative if (n,k)=1(n, k) = 1 and kk is odd, and negative otherwise.

Want a route through all this instead of 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 reproduced verbatim; metadata (topic, difficulty) added by this project.