Maths Olympiad Prep

Library / /71 of 87

Combinatorics Difficulty 7.0 National Olympiad, round 2 Prove it Russia

Petya chose 100 pairwise distinct positive real numbers, each less than 11, and arranged these numbers on a circle. Then he performs the following moves. By one move he takes some three consecutive numbers a,b,ca, b, c (in this order) and replaces the middle number bb by ab+ca - b + c. Find the greatest possible kk such that Petya can choose initial numbers and perform several moves so that in the resulting arrangement there are kk integers.

Solution

Estimate. We will show that the number of integers never exceeds 5050.
We will track the differences between each number and the next one in clockwise order. If three consecutive numbers were aa, bb, and cc, their differences were aba-b and bcb-c. After applying the operation to bb, the numbers become aa, ab+ca-b+c, and cc, with differences a(ab+c)=bca - (a-b+c) = b-c and (ab+c)c=ab(a-b+c)-c = a-b. Thus, the operation simply swaps two adjacent differences. Initially, all differences were non-integer, so they remain non-integer at all times. Therefore, two integers can never appear consecutively, meaning their count cannot exceed 5050.

Example. First, arrange the numbers 0.10.1 and 0.20.2 alternately in a circle. If we perform the operation on each 0.20.2, it will be replaced by 0.10.2+0.1=00.1 - 0.2 + 0.1 = 0, making every other number an integer.

Now, we need to adjust the example so that all numbers become distinct. To do this, it is sufficient to add a small unique value to each 0.10.1 and to each 0.20.2 the sum of the values added to its neighbors. For instance, choosing t=0.001t = 0.001, we can add to consecutive 0.10.1s the numbers 0,t,2t,,47t,48t,50t0, t, 2t, \dots, 47t, 48t, 50t; then, to the 0.20.2s, we add t,3t,5t,,95t,98t,50tt, 3t, 5t, \dots, 95t, 98t, 50t. As a result, all numbers will become distinct.

The explicitly constructed example looks as follows:
0.1 0.2001 0.1001 0.2003 0.1002 0.2005 0.1003  0.1047 0.2095 0.1048 0.2098 0.105 0.205 0.1 \ 0.2001 \ 0.1001 \ 0.2003 \ 0.1002 \ 0.2005 \ 0.1003 \ \dots \\ \dots \ 0.1047 \ 0.2095 \ 0.1048 \ 0.2098 \ 0.105 \ 0.205

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.