MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 :)

share|cite|improve this question

closed as too localized by Mark Sapir, Bill Johnson, Douglas Zare, Igor Rivin, Andreas Thom Jan 7 '12 at 20:44

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

up vote 2 down vote accepted

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$,


$\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.

share|cite|improve this answer
Thanks a lot :) I'm sorry if the question isn't suitable, I'm still a newbie (which is quite deducible from my reputation :D). Actually the problem is from a past local Math Olympiad. Anyhow, thanks again for the answer! – somethingsomething Jan 7 '12 at 20:13

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