2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ answer can be found here: artofproblemsolving.com/community/c6h607378p3609497 $\endgroup$ – Stephen Aug 16 '15 at 22:23
  • 2
    $\begingroup$ I checked that forum before posting but that answer doesnt seem to be correct $\endgroup$ – edwinisaac Aug 16 '15 at 22:24
  • $\begingroup$ @edwinisaac What do you think is wrong with that answer in the forum? It looks reasonable to me. $\endgroup$ – Calvin Lin Aug 17 '15 at 22:34
  • $\begingroup$ I double checked and now I understand and is correct . I thought that the lemma 1 using the sum of k segment was bad. Your solution is more clear. Thanks ! $\endgroup$ – edwinisaac Aug 17 '15 at 23:12
1
$\begingroup$

Label the points in clockwise order $ v_1, v_2, \ldots v_{2014}$. We will do a ton of double counting.

For a quadruple of integers $(a, b, c, d)$ with $a+b+c+d = 2014$ and $ a, b, c, d \leq 1012$, consider the 2014 convex quadrilaterals of the form $v_i, v_{i+a}, v_{i+a+b}, v_{i+a+b+c}$ where $i = 1$ to 2014.
Do the same for a triple of integers $(a,b,c), a+b+c = 2014$ defining a triangle.

Now, consider the following types of polygons:

First type: For every pair of distinct positive integers $a < b \leq 503,$ consider the 2014 quadrilaterals $(a, b, 1007-a, 1007-b)$. There are $2014 \times {503 \choose 2}$ polygons here. Multiply this by 1005 times (you will see why later).

Second type: For every positive integer $ c \leq 503$, consider the 2014 triangles $(c, 1007-c, 1007)$. There are $2014 \times 503 $ triangles here. Multiply this by 502 times (you will see why soon).

Now, let's count the number of times each line segment appears in these polygons.
For $ n \leq 503$, it appears 502 * 1005 times in the first type, and 1 * 502 times in the second type.
For $504 \leq n \leq 1006$, it appears 502 * 1005 times in the first type, and 1 * 502 in the second type.
For $n=1007$, it appears 1006 * 502 times in the second type.
Hence, we double-counted each line $1006 \times 502$ times.

The maximum sum of edges of each of these polygons is 1. Now, consider all of these polygons together. Hence, the max possible sum of all the edges is $ \frac{ 2014 \times {503 \choose 2} \times 1005 + 2014 \times 503 \times 502} { 1006 \times 502} = \frac{ 1007^2 }{ 2} $.

Conversely, it is clear how to construct such a polygon, by giving each edge of length $n$ the value of $ \frac{n}{2014}$. This satisfies the equality conditions listed above, and thus has the sum we want.


Note: The number to multiply by is determined after setting up the types, to ensure that we get a constant sum for these edges. Just set up the simultaneous equation and you will see why 1005, 502 were selected.

$\endgroup$
3
  • $\begingroup$ After your comment on my post, it seems as if this is the way to go. I was getting to the point of needing to consider quadrilaterals. $\endgroup$ – Mark Bennet Aug 17 '15 at 15:58
  • 1
    $\begingroup$ @MarkBennet Here is a problem I just created, which has a similar setup, but screws with your symmetry argument intentionally. Have fun with it! $\endgroup$ – Calvin Lin Aug 17 '15 at 17:02
  • $\begingroup$ I like that a lot. $\endgroup$ – Mark Bennet Aug 17 '15 at 17:13
1
$\begingroup$

Call an assignment of real numbers to edges valid if it satisfies the criteria in the question. Call a valid assignment maximal if the sum of real numbers on the edges is maximal.

Label the edges in some way with integers so that an assignment $A=\{a_i\}$. Note that if $A, B$ are two valid assignments and $0\le \lambda \le 1$ then $\lambda A+(1-\lambda) B=\{\lambda a_i+(1-\lambda) b_i\}$ is also valid. If $A$ and $B$ are maximal, so is a convex combination of this kind (because the sums of the $a_i$ and $b_i$ must be equal).

Now suppose we have a maximal assignment. Consider the effect of a "rotation" where the label joining points (labelled consecutively clockwise) $p_i$ and $p_j$ is moved to $p_{i+1}:p_{j+1}$ (reducing by $2014$ if necessary). This rotated assignment is also maximal. Rotation preserves convexity because it preserves the order of the vertices.

There are $2014$ rotations of every maximal assignment. Because we can take convex combinations of assignments we can take the average of the rotations of one such maximal assignment. The average has the property that every segment of the same length (i.e. for which $|i-j|$ has the same value with appropriate adjustments modulo $2014$ to obtain a value for the length $\le 1007$) has the same real number assigned. So there is a symmetrical maximum.

Then show by choosing the outer polygon that the maximal assignment in a symmetrical configuration for edges of length $1$ is $\frac 1{2014}$ and then show that for length $r$ is $\frac r{2014}$ (use the segment of length $r$ to cut off a corner of the $2014$-gon). You just need to show that the sum of the lengths of a convex polygon is $\le 2014$ and then sum all the segments (with care about not double-counting diagonals when $n$ is even).

[see comments, the above argument doesn't prove that this particular symmetric pattern is maximal - Note the square with labels zero on the sides and $1$ on the diagonals which is just as good as the square with labels $1/4$ on the sides and $1/2$ on the diagonals]

Calvin Lin's answer shows how to show maximality without needing symmetry - so it seems that the symmetry argument may at best be a diversion from the answer. If I find an improvement I'l, share it.

$\endgroup$
4
  • 1
    $\begingroup$ It looks good up to the 2nd last paragraph, which is the crux of your argument. Why must the maximal assignment have the convex hull sum to 1? It could be that by reducing that value/sum, we could increase a bunch of stuff elsewhere. As such, I believe this is currently incorrect. $\endgroup$ – Calvin Lin Aug 17 '15 at 14:40
  • $\begingroup$ @CalvinLin That is true - concretely a square could have diagonals labelled $1$ and sides labelled zero - that doesn't change the sum of labels above $2$ but it does require an extra argument. I'll leave the argument up with an edited comment and think about it - it is neat to get the symmetry. $\endgroup$ – Mark Bennet Aug 17 '15 at 14:49
  • $\begingroup$ I disagree. The "there is no way to improve this bound" kind of arguments is often just a hand-waving approach with no real basis. I might believe it if you add in some kind of smoothing argument (but also doesn't assume that the n/2014 case is maximal). $\endgroup$ – Calvin Lin Aug 17 '15 at 15:31
  • $\begingroup$ @CalvinLin I was agreeing with you that this doesn't work as it stands. $\endgroup$ – Mark Bennet Aug 17 '15 at 15:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.