75th NMO Selection Tests

We will show that the number sought is $n-1$ for $n\ne 4$ and $2$ if $n=4$.

For $n=3$ and $n=4$, it can be easily verified that the answer is $2$. Suppose now that $n\ge 5$. Denote by $a_{XY}$ the number written on segment $XY$.

If we label the vertices of the regular polygon as $A_1,A_2,\dots ,A_n$ and set $a_{A_i{A}_j}=|i-j|$ for all $i\ne j$, then the condition of the problem is satisfied, so the number sought for is at most $n-1$.

To prove equality, suppose by contradiction that the number sought for is at most $n-2$. Let $d$ be the greatest value John writes on some segment, and let $A,B$ be vertices such that $a_{AB}=d$. Suppose $d$ is written on the segment with minimal distance between the vertices among all segments with value $d$.

We make the following two observations:

1. There do not exist three vertices $A_1,A_2,A_3$ such that $a_{A{A}_1}=a_{A{A}_2}=a_{A{A}_3}$ (otherwise, it would follow that $a_{A_1{A}_2}=a_{A_1{A}_3}=a_{A_2{A}_3}$, which is impossible because the sum rule, according to the hypothesis, would no longer be valid for triangle $A_1{A}_2{A}_3$).

2. For any point $X$ different from $A$ and $B$, we have $d=a_{AX}+a_{BX}$ since $d$ is maximum; in particular, $a_{AX}<d$.

Since, by assumption, there are at most $n-2$ distinct values, the pigeonhole principle implies that there exist points $C$ and $D$ such that $a_{AC}=a_{AD}=x$, with $x<d$ (according to Observation 2).

We observe that the rule for writing the numbers on segments implies: in triangle $ACD$ we have $a_{CD}=2x$; in triangle $ABD$ we have $a_{BD}=d-x$; in triangle $ABC$ we have $a_{BC}=d-x$. Therefore, from triangle $BCD$, we obtain that $2x=(d-x)+(d-x)$, hence $x=\frac{d}{2}$ (in particular, $d$ is even).

Now, looking at the $n-2$ numbers on the segments emerging from $A$, we can see that the only value that repeats is $\frac{d}{2}$ (as shown in the previous paragraph) and it cannot appear three times (by Observation 1). Therefore, there are $n-2$ distinct numbers, and according to the assumption, these must be all the numbers used by John.

Since $n\ge 5$, there exists a vertex $E$ different from the vertices $A,B,C,D$. Let $y=a_{AE}\ne \frac{d}{2}$. Since $a_{BE}=d-y$, it follows that $d-y$ appears among the $n-2$ values on the segments emerging from $A$. Without loss of generality, we may assume that $y>\frac{d}{2}$ because $\max (y,d-y)>\frac{d}{2}$.

We look at triangle $ACE$ and observe that $a_{CE}\in \{y+\frac{d}{2},y-\frac{d}{2}\}$. Since $d$ is the maximum, and $y+\frac{d}{2}>d$, it follows that $a_{CE}=y-\frac{d}{2}$, and similarly, $a_{DE}=y-\frac{d}{2}$.

Finally, looking at triangle $CDE$, we have $a_{CD}=2(y-\frac{d}{2})<d$, but also $a_{CD}=2\cdot \frac{d}{2}=d$, a contradiction. (In triangle $ACD$ we have $a_{AC}=a_{AD}=\frac{d}{2}$, hence $CD=d$)

Therefore, there cannot be only $n-2$ values, which implies that the required number is $n-1$.