Let $n \geq 3$ be an integer. John and Mary play the following game: First John labels the sides of a regular $n$-gon with the numbers $1, 2,\ldots, n$ in whatever order he wants, using each number exactly once. Then Mary divides this $n$-gon into triangles by drawing $n-3$ diagonals which do not intersect each other inside the $n$-gon. All these diagonals are labeled with number $1$. Into each of the triangles the product of the numbers on its sides is written. Let S be the sum of those $n - 2$ products. Determine the value of $S$ if Mary wants the number $S$ to be as small as possible and John wants $S$ to be as large as possible and if they both make the best possible choices.
Problem
Source: Middle European Mathematical Olympiad 2011 - Individuals I-2
Tags: combinatorics proposed, combinatorics
anonymouslonely
07.09.2011 19:18
if John fixed the numbers on the sides then Mary will make a partition of the $ n-gon $ such that only two triangles have two sides which are always sides in the polygon. so the sum will be $ (a-1)(b-1)+(c-1)(d-1)+F $ where $ 2F=n(n+1) $ where $ a,b,c,d $ are distinct numbers such that $ (a,b),(c,d) $ are consecutive sides of the polygon. then Mary will take $ a=1 $ and she will take the other minimum $ (c-1)(d-1)>0 $. so we have to find the maximum of the minimum of $ b_{i}b_{i+1} $ where $ b_{j} $ is a permutation of $ 0,1,...,n-1 $.
anonymouslonely
07.09.2011 19:23
this maximum have to be $ >0 $. for $ b_{i}=1 $ we obtain that the maximum is at most $ n-2 $ because it has two neighbors so John will put for example $ n-2,1,n,2,n-1,.... $. so the $ S=n(n+1)/2+n-2 $.
Swistak
07.09.2011 22:06
Not exactly. $S=\frac{n^2+3n-6}{2}$. Sum will be $(a-1)(b-1)+(c-1)(d-1)-2+F$ (which of course has long proof), and John will put for example $1, 2, n, ...$ and maximum will be $n-1$.
anonymouslonely
07.09.2011 22:21
yes,sorry for the $ -2 $... but I think you're wrong because the numbers $ b_{i} $ can also put on the sides of a $ (n-1)-gon $ and $ 1 $ will have two neighbors sides so the minimum is $ n-2 $.
veyron
08.09.2011 04:15
for $n=3, S=6$ , for $ n \ge 4,S=\frac{n^{2}+3n-8}{2} $
Swistak
08.09.2011 17:29
Guys, answer is $\frac{n^2+3n-6}{2}$ and there's no discussion about that . I got 8 points, so my solution solution seems to be correct . John should label sides with number in order: $... 7, n-3, 5, n-1, 3, 1, 2, n, 4, n-2, 6, n-4...$ (this is one from many good orders) Mary should choose pairs $(3, 1)$ and $(2, n)$ and intersect this polygon to 2 triangles which sides are $(3, 1)$ or $(2, n)$ and one diagonal and $n-4$ triangles built from 2 diagonals and one side of polygon (it's possible). In this case $S=\frac{n^2+3n-6}{2}$ and that's correst answer.
kaszubki
08.09.2011 23:27
what the heck?? I got 8 points too and my answer was $\frac{n^2 + 6n - 8}{2}$ for $n\geq 4$...
anonymouslonely
09.09.2011 06:04
I think swistak is right... in my proof I omitted that the pairs of sides can't have common sides so the minimum was $ n-1 $ and is attained. kaszubki,can you elaborate this? how do you obtain a number like that? P.S. what is the maximum number of points that you can obtain at this problem?
Swistak
10.09.2011 17:34
kaszubki, unsuccesful troll, because your answer isn't integer, when n is odd :D