$2014$ points are placed on a circumference. On each of the segments with end points on two of the $2014$ points is written a non-negative real number. For any convex polygon with vertices on some of the $2014$ points, the sum of the numbers written on their sides is less or equal than $1$. Find the maximum possible value for the sum of all the written numbers.
Problem
Source:
Tags: combinatorics unsolved, combinatorics
24.09.2014 16:48
25.09.2014 00:40
Let's solve the general case for $n$ even. We say that a segment with endpoints on the $n$ points in the circle is a $k$-segment if it separates the circle into two parts, with the part with the minimum quantity of points having $k-1$ points (for example, any side of the $n$-agon is a $1$-segment, and any diameter is a $n/2$-segment. For $k=1,2,...,n/2$, let $A_k$ be the sum of the numbers in all $k$-segments. We'll proof the following: Lemma 1: If $k_1, \dots, k_l$ are positive integers with $l \ge 3$, $k_1, \dots, k_l < n/2$ and $k_1 + k_2 + \dots +k_l =n$, then $A_{k_1} + \dots + A_{k_l} \le n$. Proof: Consider all the $n$ convex polygons that have $l$ sides $a_1, \dots, a_l$, in clockwise orientation, and such that $a_1$ is a $k_1$-segment, $a_2$ is a $k_2$ segment and so on. Every $k_1$ side appears exactly once on those polygons, Every $k_2$ side appears exactly once on those polygons, and so on. Thus, the sum of the numbers on those $n$ polygons is exactly $A_{k_1} + \dots + A_{k_l}$. But this sum is at most $n$, so $A_{k_1} + \dots + A_{k_l} \le n$. Lemma 2: If $k_1, \dots, k_l$ are positive integers with $l \ge 3$, $k_1, \dots, k_{l-1} < n/2$, $k_l=n/2$ and $k_1 + k_2 + \dots +k_l =n$, then $A_{k_1} + \dots + A_{k_{l-1}}+2A_{k_l} \le n$ Proof: Similar to Lemma 1, but you must note that each $n/2$-segment appears twice on the $n$ polygons, instead of once. With that in mind, we have that, from Lemma 1, $A_t+A_{n/2-t}+A_t+A_{n/2-t} \le n$, for all $t=2,3,...,n/2-1$, hence $A_t+A_{n/2-t} \le n/2$, and summing this from $t=2$ to $t=n/2-1$, we have, calling $S=A_1+A_2+...+A_{n/2}$ $(S-A_1-A_{n/2})+(S-A_{n/2-1}-A_{n/2}) \le (n/2-2).n/2 \Rightarrow$ $\Rightarrow 2S \le n^2/4 +(A_1 + A_{n/2-1} +A_{n/2}-n)$ But from Lemma 2, $A_1 + A_{n/2-1} +A_{n/2} \le n$, where we finnaly get $2S \le n^2/4 \Rightarrow S \le n^2/8$. The maximum is really $n^2/8$, because if each $k$-segment have $k/n$ written on it, every polygon'll have the sum of the numbers on their sides at most 1, because if the polygon contains the center of the circunference, it's easy to see that the sum is exactly 1, and if not, the sum will be twice the number of points of the minor arc determined by the longest side (includind vértices), and that's at most 1. Now, notice that $A_1=1; A_2=2; ...;A_{n/2-1}=n/2-1$ and $A_{n/2}=n/4$. Therefore, the sum of all numbers is $(n/2-1)(n/2)/2+n/4=n^2/8$, finishing the problem.