Maths Olympiad Prep

Track / Stage 6 / 74 of 400 #1074 of 1964

Problem 1074

National olympiad, first round
Combinatorics Difficulty 6.1 Prove it

8.134 On a circle, there are 20 real numbers. It is allowed to replace three consecutive numbers x,y,zx, y, z with x+y,−y,z+yx+y, -y, z+y (still placed in the original order). If initially, the 20 numbers 1,2,⋯ ,9,10,−1,−2,⋯ ,−9,−101, 2, \cdots, 9, 10, -1, -2, \cdots, -9, -10 are placed in a clockwise direction, can the array be transformed into 10,9,⋯ ,2,1,−10,−9,⋯ ,−2,−110, 9, \cdots, 2, 1, -10, -9, \cdots, -2, -1 after several such transformations?

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

[Solution] It can be achieved. Imagine placing 20 integers x1,x2,⋯ ,x20x_{1}, x_{2}, \cdots, x_{20} on a circle, such that the differences x2−x1,x3−x2,⋯ ,x20−x19,x1−x20x_{2}-x_{1}, x_{3}-x_{2}, \cdots, x_{20}-x_{19}, x_{1}-x_{20} are exactly the original array 1, 2,⋯ ,9,10,−1,−2,⋯ ,−9,−102, \cdots, 9,10,-1,-2, \cdots,-9,-10. Since the sum of the original array is 0, this is possible. For example, we can take 0,1,3,6,10,15,21,28,36,45,55,54,52,49,45,40,34,27,19,100,1,3,6,10,15,21,28,36,45,55,54,52,49,45,40,34, 27,19,10. It is not difficult to verify that the transformation (x,y,z)⟶(x+y,−y,z+y)(x, y, z) \longrightarrow(x+y,-y, z+y) in the original array is equivalent to the transformation (xk,xk+1)⟶(xk+1,xk)\left(x_{k}, x_{k+1}\right) \longrightarrow\left(x_{k+1}, x_{k}\right) in the new array, where y=xk+1−xky=x_{k+1}-x_{k}, i.e., the allowed transformation in the original array becomes the exchange of two adjacent numbers in the new array. The new array can clearly be transformed into the following order through several exchanges of adjacent numbers: x1,x20,x19,⋯ ,x2x_{1}, x_{20}, x_{19}, \cdots, x_{2}, at which point the corresponding difference array x20−x1,x19−x20,⋯ ,x2−x3,x1−x2x_{20}-x_{1}, x_{19}-x_{20}, \cdots, x_{2}-x_{3}, x_{1}-x_{2} is exactly 10,9,⋯ ,2,1,−10,−9,⋯ ,−2,−110,9, \cdots, 2,1,-10,-9, \cdots,-2,-1.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.