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

Solution 1:

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

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

Solution 2:

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

Solution 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$).