Let $n \ge 3$ be an integer. On a circle, there are $n$ points. Each of them is labelled with a real number at most $1$ such that each number is the absolute value of the difference of the two numbers immediately preceding it in clockwise order. Determine the maximal possible value of the sum of all numbers as a function of $n$. (Walther Janous)
Problem
Source: 2021 Austrian Federal Competition For Advanced Students, Part 1 p3
Tags: combinatorics
building
06.06.2021 06:40
We claim that the answer is $\tfrac{2}{3}n$ when $3 \mid n$ and $0$ otherwise.
To show this, let $a_1, \dots, a_n$ be the numbers in clockwise order, with $a_n$ the maximum of the numbers. Note that all of the numbers are nonnegative.
Claim: $a_n \leq \max\{a_1, a_2\}$.
Proof: Suppose not. Let $i$ be the smallest index such that $a_i > \max\{a_1, a_2\}$. (Clearly $i \geq 3$.) But then $\max\{a_1, a_2\} < a_i = |a_{i-1} - a_{i-2}| \leq \max\{a_{i-1}, a_{i-2}\}$ (where the last step follows from the fact that $a_{i-1}$ and $a_{i-2}$ are nonnegative). This implies either $a_{i-1}$ or $a_{i-2}$ is greater than $\max\{a_1, a_2\}$, contradicting our assumption that $i$ was minimal.
Since we assumed $a_n$ was the maximum, it follows that either $a_1 = a_n$ or $a_2 = a_n$. In either case, we find that the numbers repeat in a pattern of period $3$:
$$a_n, a_n, 0, a_n, a_n, 0, \dots$$We can have $a_n \neq 0$ if and only if $3 \mid n$ (otherwise, the pattern won't line up once you wrap around the circle). If $3 \mid n$, we can maximize the sum by taking $a_n = 1$, which gives a sum of $\tfrac{2}{3}n$. If $3 \nmid n$, then our only choice is to take $a_n = 0$, giving a sum of $0$, as claimed.