
C3. Fix an odd integer $n>1$. For a permutation $p$ of the set $\{1,2, \ldots, n\}$, let $S$ be the number of pairs of indices $(i, j), 1 \leq i \leq j \leq n$, for which $p_{i}+p_{i+1}+\cdots+p_{j}$ is divisible by $n$. Determine the maximum possible value of $S$.

CroatiA


Solution 1. For visual clarity, write the numbers $p_{1}, \ldots, p_{n}$ in a row, and put a dot between any two of them, and also to the left and to the right of the row. We say that a pair of dots is good is $n$ divides the sum of the numbers between them. So we need to find the maximal possible number of good pairs.

Let $n=2 k-1$; we claim that the answer is $\binom{k+1}{2}$. A confirming example is constructed as follows. Partition the numbers $1,2, \ldots, n$ into $k-1$ pairs $\{1, n-1\},\{2, n-2\}, \ldots,\{k-1, k\}$ and a singleton $\{n\}$; the sum in each part is $n$. Arrange the numbers so that the elements of each pair are adjacent; paint red a dot between the two numbers from the same pair. Then each pair of non-red dots is good, so there are at least $\binom{k+1}{2}$ good pairs.

Now we show that this is indeed the maximal possible number of good pairs. For this purpose, notice first that removal of the number $n$ from the row does not change goodness of any pair; it may, however, glue together some good pairs, which we will take care of later. Hence, we first consider a permutation $q_{1}, \ldots, q_{n-1}$ of $1,2, \ldots, n-1$ and estimate the number of good pairs for such permutation.

Split all entries in the new row into $k-1$ pairs $P_{1}, \ldots, P_{k-1}$ of adjacent entries. Say that a pair of dots is of type $(i, j)$ if the space between them meets exactly the pairs $P_{i}, \ldots, P_{j}$. Now we estimate the number of good pairs of each type separately.

Case 1: types $(i, j)$ with $i=j$. Such pair may be good only if it encloses a pair of complementary numbers $(s, n-s)$, i. e., if $P_{i}$ contains these numbers in some order. Let $d \leq k-1$ be the number of such pairs $P_{i}$.

Case 2: types $(i, j)$ with $i<j$. There are four pairs of dots of any such fixed type. Let $a$ be the left entry in $P_{i}$, and $b$ be the right entry in $P_{j}$. Then the four sums have the forms $s, s+a, s+b$, and $s+a+b$, for some $s$. One of these sums may be divisible by $n$. However, two of the four sums may be divisible by $n$ only if $a+b=n$; in this case, $P_{i}$ and $P_{j}$ contain complementary numbers $a$ and $b$, respectively. Since the total number of complementary pairs is $k-1$, the number of such pairs $(i, j)$ is at most $(k-1)-d$; hence the total number of good pairs of the considered types is at most $\binom{k-1}{2}+(k-1)-d$.

Combining the bounds above, we get that the number of good pairs in the new situation is at most $d+\binom{k-1}{2}+(k-1)-d=\frac{1}{2} k(k-1)$.

It remains to check how many good pairs are lost when $n$ has been removed. These are exactly the pairs of dots such that $n$ stands at one of the ends of the segment flanked by the dots; one of these segments consists of $n$ alone. Assume that there are $a$ numbers to the right of $n$ (including $n$ itself). Then, only every second of them can be the other end of a segment enclosed by a good pair, hence there are at most $\left\lfloor\frac{1}{2}(a+1)\right\rfloor$ such pairs. Similarly, since there are $b=n+1-a$ numbers to the left of $n$, there are at most $\left\lfloor\frac{1}{2}(b+1)\right\rfloor$ corresponding good pairs. The segment covering $n$ alone is counted twice, so the total number of lost good segments is at most $\left\lfloor\frac{1}{2}(a+1)\right\rfloor+\left\lfloor\frac{1}{2}(b+1)\right\rfloor-1 \leq\left\lfloor\frac{1}{2}(a+1)+\frac{1}{2}(b+1)\right\rfloor-1=\left\lfloor\frac{1}{2}(a+b)\right\rfloor=\frac{1}{2}(n+1)=k$.

Thus, the total number of good pairs is at most $\frac{1}{2} k(k-1)+k=\frac{1}{2} k(k+1)$, as required.
