Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!)

share|improve this question
4  
You can use the same idea as in that earlier problem to get some elements of $A_{k,n}$. All $i$ and $n-i$, with $i<k$ and either $n=3i$ or $n<2i$ will be in $A_{k,n}$. –  polkjh Jan 21 '13 at 11:11
2  
No, this is not exhaustive. For example, if $n<2k$, then $1,n-1 \in A_{k,n}$. I am not sure if adding these covers the entire $A_{k,n}$ either. We can get some conditions on $A_{k,n}$ by placing some particular $k$ integers in the circle. For example, let the $k$ integers be $1,1,\ldots,1,n-k+1$. From this we get that $A_{k,n} \subseteq \{1,2,\ldots,k-1\} \cup \{n-k+1,n-k+2,\ldots,n\}$. –  polkjh Jan 23 '13 at 19:33

3 Answers 3

up vote 3 down vote accepted
+250

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

share|improve this answer
    
+1 Very nice solution! –  Erick Wong Jan 29 '13 at 3:51

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

share|improve this answer
    
$+1$ Nice idea! –  polkjh Jan 26 '13 at 7:49
2  
Some simple observations for the next-highest case: $A_{k,2k}$ contains only even integers (take the circle of all $2$s) and if $k$ is even, it contains only multiples of $4$ (take alternating $1$s and $3$s). Also, $A_{k,n}$ is always disjoint from the interval $[k,n-k]$ (take all $1$s except for one large). What other designs can produce negative results? –  Erick Wong Jan 27 '13 at 21:26

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

share|improve this answer
1  
It turns out for all $k \le 17$ that $A_{k,2k+1}$ is precisely equal to the set of non-units mod $2k+1$. Admittedly there isn't much variety in factorization for such small numbers (I doubt I can reach $2k+1 = 3\cdot 5\cdot 7$), but I'm surprised by the level of number-theoretic content here. –  Erick Wong Jan 27 '13 at 23:07
2  
It is true that $A_{k,2k+1}$ is always the nonunits. –  zyx Jan 28 '13 at 12:51
1  
It is also the case that $k \leq (n/3)$ is never enough to force any value less than $n$ into $A_{k,n}$, and $k > (n/2)$ forces all. –  zyx Jan 29 '13 at 7:25

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.