NMO Selection Tests

We will show that the number sought is $n-1$ for $n \neq 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 \neq 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_{AA_1} = a_{AA_2} = a_{AA_3}$ (otherwise, it would follow that $a_{A_1A_2} = a_{A_1A_3} = a_{A_2A_3}$, which is impossible because the sum rule, according to the hypothesis, would no longer be valid for triangle $A_1A_2A_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$.