Minimum Permutation Sum

Consider the ten sums $x_1+\dots +x_{10},x_{11}+\dots +x_{20},\dots ,x_{91}+\dots +x_{100}$ . The 100 terms in these sums are disjoint, and their sum is $\sum_{i=1}^{100}x_i=5050$ . It follows by Pigeonhole Principle, that one of these sums is at least the average, that is, $\frac{5050}{10}=505$ .

We now prove that $505$ is achievable. Draw a $10$ by $10$ table $T$ as follows:

$\begin{array} {l l l l l l } 100 &81 &80 & \dots &20 &1\\ 99 &82 &79 &\ldots& 19 &2\\ 98 &83 &78 &\ldots &18& 3\\ 97 &84 &77 &\ldots &17 &4\\ 96 &85 &76 &\ldots &16 &5\\ 95 &86 &75 &\ldots& 15 &6\\ 94 &87 &74 &\ldots &14 &7\\ 93 &88 &73 &\ldots& 13 &8\\ 92 &89 &72 &\ldots &12 &9\\ 91 &90 &71 &\ldots &11 &10\\ \end{array}$

Take this table and take the $x_i$ going right, in order, for every row. That is, our sequence is now $100,81,80,\dots ,20,1,99,82,79,\dots ,19,2,98,\dots$ . I claim that this works. Let $s_i=x_i+\dots +x_{i+9}$ .

We can verify that the first initial sum $s_1 = 505$ . But note that by design, $s_{i+1}=s_i\pm 1$ , with $\pm$ constantly alternating. It follows that all sums are $s_i = 505$ for $i$ odd and $s_i = 504$ for $i$ even, and we're done.

First, we establish a bound. Consider the 10 sets $\begin{aligned} &\{x_1,x_2,x_3,\cdots,x_{10}\} \\ &\{x_{11},x_{12},x_{13},\cdots,x_{20}\} \\ &\cdots \\ &\{x_{91},x_{92},x_{93},\cdots,x_{100}\} \\ \end{aligned}$ All 100 elements are distinct, and they add to $1+2+3+\cdots+100=5050$ , so the minimum of the maximum element sum of one of these sets is $\dfrac{5050}{10}=505$ . Therefore, the answer is at least 505.

Now, we show that 505 is achievable. Consider the 10 ordered sets $\begin{aligned} S_1&=\{100,99,98,\cdots,91\} \\ S_2&=\{81,82,83,\cdots,90\} \\ &\cdots \\ S_{0}&=\{1,2,3,4,5,6,7,8,9,10\} \end{aligned}$

Consider the permutation where the elements with $i\equiv k\pmod{10}$ are, in order, the elements of $S_{k}$ . We claim that this permutation has a maximum sum of 10 consecutive elements of 505. First, note the first 10 elements are $100,81,80,61,60,41,40,21,20,1$ , with a sum of $505$ . Now, removing the 1st element and adding the 11th, we remove the 1st element of $S_1$ and add the 2nd, which is 1 less, making the new sum 504. Removing the 2nd element and adding the 3rd, we remove the 1st element of $S_2$ and add the 2nd, which is one more, making the new sum 505. In this way, we always replace an element with the number alternating above and below, and so the sum alternates 505,504,505,504,... Thus, the minimum of $\boxed{505}$ is indeed achievable.

To hopefully make things more clear, the permutation is (python, not written out) $(100,81,80,61,60,41,40,21,20,1,99,82,79,62,59,42,39,22,19,2,98,83,78,63,58,43,38,23,18,3,97,84,77,64,57,44,37,24,17,4,96,85,76,65,56,45,36,25,16,5,95,86,75,66,55,46,35,26,15,6,94,87,74,67,54,47,34,27,14,7,93,88,73,68,53,48,33,28,13,8,92,89,72,69,52,49,32,29,12,9,91,90,71,70,51,50,31,30,11,10)$

Motivation: After I established the bound, I tried to make the sums as close as possible. Two consecutive sums cannot be equal, so I made them differ by 1. The construction followed.

The first thing to do is to translate the math symbols into something that is easy to conceptualize. The problem is asking for the smallest possible value of the maximum sum of $10$ consecutive elements in any of the $100!$ permutations of the first $100$ positive integers.

After I figured that out, I thought that if a maximum sum was being taken, then the number $100$ would probably be involved. The best way to minimize the sum of $100$ and one of the first $99$ positive integers is to use the number $1$ . This gives a sum of $101$ , and it is the minimum possible maximum sum of two consecutive elements over all of the permutations. I applied the same logic to a $98$ -element sequence containing integers in the range $[2,99]$ and once again got a result of $101$ for the minimum maximum sum of two consecutive elements over all permutations.

I continued using this logic for the problem and arrived at the set $S_1=\{100, 1, 99, 2, \ldots , n, 101-n, \ldots , 51, 50\}$ . However, another possible set such that $x_{2k}=101-x_{2k-1}$ when $k$ is a positive integer is $S_2=\{1, 100, 2, 99, \ldots , n, 101-n, \ldots, 50, 51\}$ . We must consider the maximum sums of these two sets. Something that needs to be done when taking maximum sums is considering sums that begin on $x_{2k}$ $\textit{and}$ sums that befin on $x_{2k-1}$ . When you consider the maximum sums of the sequences, the following is found.

$S_1=\{100, 1, 99, 2, \ldots , n, 101-n, \ldots , 51, 50\}\rightarrow505$ (start on $x_1$ ) $S_2=\{1, 100, 2, 99, \ldots , n, 101-n, \ldots , 50, 51\}\rightarrow510$ (start on $x_2)$

The smaller one of these is $505$ , so the answer to the problem is $\boxed{505}$

So why does my original reasoning work? How did I come up with $S_1$ and $S_2$ ? Try to come up with a sequence of the sums of two consecutive elements of $S_1$ (called $S_+$ ). This sequence will be $50$ repeated occurrences of the number $101$ . We are trying to find if this is the minimal sum. If you switch two elements of $S_1$ , one element of $S_+$ will go up and another will go down. No matter what happens, $S_+$ will always have an average of its elements equal to $101$ . If a local decrease of elements occurs to lower the local average by any amount, then the average of the rest of the elements will go up. There will always be a set of ten consecutive elements that will have an average greater than $101$ if another set of ten consecutive elements has its average go down. So the average of elements $x_{2k-1}$ and $x_{2k}$ will always be $101$ . This would repeat $5$ times, so the answer is $101\times5=\boxed{505}$

Think of the Permutation: {100, 1, 99, 2, 98, 3, 97, 4, ............. 51,50}.

Maximum sum of 10 consecutive terms in this permutation is 505.

Sum of positive integers from 1 to 100 = 5050

So we cannot reduce sum of 10 consecutive terms to less than 5050/10 = 505

Hence 505 is the minimum.

The answer is 505. To establish an upper bound, just use ${100,1,99,2,97,3,...,52,49,51,50}$

To establish a lower bound, partition the number into 10 groups of 10. Using Gauss's theorem sorry, inside joke:) they sum to 5050, which implies that at least one is greater than or equal to 505.

This clearly generalizes to any set size that's a multiple of 10.

For some positive real numbers, $\min \le average \le max$ .

In the problem average of the set is $505$ and all numbers are positive and distinct. Again cardinality of the set $100$ is an even multiple of $10$ (total number of terms taken at a time for the sum operation). So, minimum among the maximum values of consecutive ten numbers is $505$ as the sum can not less than the average value. Answer is $\boxed{505}$ .