Given that $X = \{0, 1, 2, ..., 7, 8, 9\}$, and $P$ is a permutation on $X$. Let $M(P)$ be the maximum sum of 3 consecutive elements. For example, if $P = (0, 2, 4, 1, 5, 7, 9, 3, 8, 6)$, then $M(P)$ is the maximum integer among $6, 7, 10, 13, 21, 19, 20, 17$ (which are the sums of each 3 consecutive elements, respectively). In the example above, $M(P) = 21$. Prove that there exists no permutation $P$ that satisfies $M(P) = 12$. Also, find a way to construct a permutation that satisfies $M(P)=13$. Any help would be extremely appreciated :)



Maximum sum of 3 consecutive numbers in a permutation
I am sorry, but this is certainly not a research question, and hence (as far as I understand the purpose of this forum) not a suitable question for mathoverflow. I suppose this thread will be closed within the next few minutes (and rightfully so).


However, since I read the question and started thinking about it, here is a solution to your problem (which, I hope, is not your homework):


You have $M(P) = 13$ for $(9,4,0,8,3,2,7,1,5,6)$ and it is not hard to prove that you have
$M(P) > 12$ for all $P$: Assume that we have $M(P) \leq 12$ for some $P = (n\_0,\ldots,n\_9)$. Then,


$\underbrace{n\_1 + n\_2 + n\_3}\_{\leq 12} + \underbrace{n\_4 + n\_5 + n\_6}\_{\leq 12} + \underbrace{n\_7 + n\_8 + n\_9}\_{\leq 12} \leq 36$,


and


$\underbrace{n\_0 + n\_1 + n\_2}\_{\leq 12} + \underbrace{n\_3 + n\_4 + n\_5}\_{\leq 12} + \underbrace{n\_6 + n\_7 + n\_8}\_{\leq 12} \leq 36$.


However, since $P$ is a permutation, we must have 


$\sum\_{i=0}^9 n\_i = 0 + 1 + \ldots + 9 = 45$.


So the two inequalities above imply $n\_0 = 9$ as well as $n\_9 = 9$, a contradiction.


