Permutations with small maximal $k$-consecutive sums

Abstract

Let $n$ and $k$ be positive integers with $n>k$. Given a permutation $({\pi }_1,\dots ,{\pi }_n)$ of integers $1,\dots ,n$, we consider $k$-consecutive sums of $\pi$, i.e., $s_i:={\sum }_{j=0}^{k-1}{\pi }_{i+j}$ for $i=1,\dots ,n$, where we let ${\pi }_{n+j}={\pi }_j$. What we want to do in this paper is to know the exact value of $$\mathrm{msum}(n,k):=\min \left\{\max \{s_i:i=1,\dots ,n\}-\frac{k(n+1)}{2}:\pi \in S_n\right\},$$ where $S_n$ denotes the set of all permutations of $1,\dots ,n$. In this paper, we determine the exact values of $\mathrm{msum}(n,k)$ for some particular cases of $n$ and $k$. As a corollary of the results, we obtain $\mathrm{msum}(n,3)$, $\mathrm{msum}(n,4)$ and $\mathrm{msum}(n,6)$ for any $n$.

15 pages, to appear in Discrete Math