Arc sums for a circle of $k$ positive integers whose total sum is $n$

Question

This problem got me thinking about the following more general scenario:

Suppose you have $k$ positive integers with total sum $n$, and you arrange them in a circle.

Given such an arrangement, you could look at different sums of consecutively placed positive integers along "arcs" of this circle. Furthermore, you could ask which numbers must always appear in an arc for a given $k$ and $n$, i.e., regardless of which $k$ positive integers summing to $n$ are chosen and how they are arranged around the circle.

Let $A_{k, n}$ be the set of numbers that necessarily appear in some arc for every circular arrangement of $k$ positive integers whose sum is $n$. (Of course, this set is nonempty iff $k \leq n$.)

Trivially, $n \in A_{k, n}$. (Proof: take the arc that corresponds to the entire circle.)

The linked problem above demonstrates that $200 \in A_{101, 300}$ using the pigeonhole principle.

Another obvious fact: given a positive integer $m < n$ with $m \in A_{k, n}$, then $n-m \in A_{k,n}$ as well.

For the linked problem above, this means that $300 - 200 = 100 \in A_{101, 300}$ too.

Of course, this latter fact is proven by taking complement arcs.

Questions:

$1.$ Has this general scenario already been studied under some other name?

$2.$ Is there an easy way to determine the elements of $A_{k,n}$ in general?

$3.$ If the answers to $1$ and $2$ are both no, what can you show for some special cases?

As a final, very simple example: $A_{n,n} = \{1, \ldots, n\}$.

(Ideally, if you are going to answer $3$, it would be with a less trivial proposition!)

Answer 1

Equivalent problem: $k$ distinct elements are selected from the integers $\mod n$; which $\mod n$ differences between pairs are forced? The equivalence is to assign, to a set of $k$ positive integers written around a circle, its set of clockwise arc sums $\mod n$, including $0$ for the empty sum.

Pairs at a difference of $d$ can be represented as an undirected graph by joining any such pair by an edge. The structure of the graph depends only on $g = \gcd(d,n)$, it is a union of $g$ disjoint cycles all of length $\frac{n}{g}$. A cycle of length $L$ can accomodate up to $\lfloor \frac{L}{2} \rfloor$ vertices not connected by an edge.

Thus $d$, and any distance with the same value of $g$, is forced if and only if $k > g \lfloor \frac{n}{2g} \rfloor$. The condition for $k$ to force $g$ is then $k > n/2$ when $2g|n$, and $k > \frac{n-g}{2}$ when $n$ and $g$ are divisible by the same power of $2$. This is the necessary and sufficient condition for values of $d$ with $(d,n)=g$ to be in the set of forced arc sums $A_{k,n}$.

Answer 2

Here's a special case: If $k \leq n < 2k$ then $A_{k,n} = \{1, 2, \ldots, n\}$.

---

The OP has already shown that $A_{n,n} = \{1, 2, \ldots, n\}$, so let's assume $k < n < 2k$.

Start at the largest positive integer on the circle. Since $n > k$, this must be at least $2$. Let $s_j$, $1 \leq j \leq kn$, be the sum of the $j$ consecutive values moving clockwise from this starting point. Note that $s_{kn}$ adds up numbers that wrap around the circle $n$ times.

Let $S = \{s_j \, |\, 1 \leq j \leq kn\}$. The values in $S$ are all distinct. Moreover, the smallest is at least $2$ and the largest is exactly $n^2$.

For any positive integer $i$, let $T = \{s_j + i \, | \, 1 \leq j \leq kn\}$. The values in $T$ are all distinct. Moreover, the smallest is at least $2+i$ and the largest is exactly $n^2+i$.

Together, $S$ and $T$ contain $2kn$ elements, all of which must be among $n^2+i-1$ values. The pigeonhole principle says that if $2kn > n^2 + i - 1$, then at least one element from $S$ and one element from $T$ must have the same value. Rearranging, this inequality is equivalent to $i < (2k-n)n + 1$. Since $2k - n \geq 1$, the inequality is true for any $i \leq n$.

So, if $1 \leq i \leq n$, there exist indices $j$ (from $S$) and $m$ (from $T$) such that $s_j = s_m + i$. But $s_j - s_m = i$ means that the sequence of integers starting at position $m+1$ and ending at position $j$ sums to $i$. Moreover, since once around the circle yields a sum of $n$, and $i \leq n$, this sequence does not go all the way around the circle. Thus if $1 \leq i \leq n$, there exists an arc sum equal to $i$.

Therefore, $A_{k,n} = \{1, 2, \ldots, n\}$ for $k \leq n < 2k$.

Answer 3

Follow-up, slightly too long for a comment: did some small experiments, and it appears (empirically) that $A_{k,2k}$ consists of exactly those integers having at least the $2$-adic valuation of $2k$ (e.g. $A_{6,12} = \{4,8,12\}$). The pattern holds up to $k\le 17$, after which my program takes more than a few minutes to run.

It seems things do get interesting when $n - 2k$ is small and non-negative. It appears that $A_{k,n} = \{n\}$ most of the time, especially when $n$ is much larger than $k$ (a precise form of this statement probably isn't hard to prove, perhaps for $n \ge 3k$).

Here's another interesting pattern:

• $A_{4,n} = \{n\}$ for all $8 \le n \le 30$, except $A_{4,9} = \{3,6,9\}$.
• $A_{5,n} = \{n\}$ for all $11 \le n \le 30$, except $A_{5,12} = \{4,8,12\}$.
• $A_{6,n} = \{n\}$ for all $13 \le n \le 30$, except $A_{6,15} = \{5,10,15\}$.
• $A_{7,n} = \{n\}$ for all $16 \le n \le 30$, except $A_{7,18} = \{6,12,18\}$.

One might naturally be tempted to conjecture that either $A_{k,n} = \{1,\ldots,n\}$ or $A_{k,n} = \{n\}$, unless $n = 2k$ or $n = 3(k-1)$. But the truth is not quite so convenient, for we also have

• $A_{7,15} = \{3,5,6,9,10,12,15\}$.

This seems to be the first example that does not consist of an arithmetic progression mod $n$ (however, note that it is precisely the set of non-units mod $15$).