Olympiad Maths Prep

Library / /27 of 33

Combinatorics Difficulty 7.2 National olympiad, round 2 Prove it Belarus

Vertices of a regular nn-gon are marked on a circumference. Integer numbers are placed at the vertices such that the difference of any two adjacent numbers equals ±1\pm 1 or 00. At a moment, simultaneously, the half-sums of each pair of the adjacent numbers are placed at the midpoints of the arcs subtending the corresponding sides of the nn-gon.
Find all possible values of nn for which after some such moves there exist a pair of opposite points, among 2n2n points thus obtained, with the same numbers at them.
(M. Karpuk)

Solution

Answer: all even nn.
The following example shows that n=2k+1n = 2k + 1 does not satisfy the problem condition. We number clockwise the vertices of the nn-gon as A0,A1,,Ak,Ak,,A1A_0, A_1, \dots, A_k, A_{-k}, \dots, A_{-1} and place the number i|i| at the vertex AiA_i. Since nn is odd, the pairs of antipodal points have the form «vertex-midpoint of an arc». But the integer numbers are placed at the vertices while the fractional numbers are placed at the midpoints of all arcs (except for the arc AkAkA_k A_{-k} at the midpoint of which the number k0k \neq 0 is placed).
Show that for n=2kn = 2k there exist antipodal points with the same numbers. We number clockwise the vertices of the nn-gon as A1,A2,,A2kA_1, A_2, \dots, A_{2k}, and let a1,a2,,a2ka_1, a_2, \dots, a_{2k} be the numbers at these vertices, respectively. For convenience we assume that A2k+1=A1A_{2k+1} = A_1 and a2k+1=a1a_{2k+1} = a_1. Consider the numbers
ak+1a1,ak+2a2,,ak+iai,,ak+(k+1)ak+1.(1) a_{k+1} - a_1, a_{k+2} - a_2, \dots, a_{k+i} - a_i, \dots, a_{k+(k+1)} - a_{k+1}. \quad (1)
The absolute value of the difference between any two adjacent terms of sequence (1) is less than or equal to 2. Indeed,
(ak+iai)(ak+i+1ai+1)ak+i+1ak+i+ai+1ai1+1=2,(2) |(a_{k+i} - a_i) - (a_{k+i+1} - a_{i+1})| \le |a_{k+i+1} - a_{k+i}| + |a_{i+1} - a_i| \le 1+1=2, \quad (2)
since, by condition, ak+i+1ak+i1|a_{k+i+1} - a_{k+i}| \le 1, ai+1ai1|a_{i+1} - a_i| \le 1 for all ii and kk. If there is zero between the terms of (1), then there are antipodal points with the same numbers.
Suppose that there is no zero in sequence (1). Since the first and the last terms of (1) have different signs (their sum is equal to 0), there are two adjacent terms ak+iaia_{k+i} - a_i and ak+i+1ai+1a_{k+i+1} - a_{i+1} with different signs. Since all terms of (1) are integer, 0 does not belongs to (1), and (2) holds, we see that exactly one of these two adjacent numbers is equal to 1 while the other is equal to -1. Therefore, their sum ak+iai+ak+i+1ai+1=1+(1)=0a_{k+i} - a_i + a_{k+i+1} - a_{i+1} = 1 + (-1) = 0, i.e., ai+ai+1=ak+i+ak+i+1a_i + a_{i+1} = a_{k+i} + a_{k+i+1}. Hence the numbers placed at the antipodal points (midpoints of the arcs Ak+iAk+i+1A_{k+i}A_{k+i+1} and AiAi+1A_iA_{i+1}) are equal. Thus all even nn satisfy the problem condition.

Looking for a route rather than 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 and solution reproduced as published; topic and difficulty added by this site.