Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Suppose that you are given a set $S$ of $k$ nonzero elements from $\mathbb{Z}_n$. Is it always possible to order the elements of $S$, say $a_1,a_2,\dots,a_k$ in such a way that the partial sums $a_1,a_1+a_2,a_1+a_2+a_3,\dots,a_1+a_2+\cdots+a_k$ are all distinct. Equivalently, you want to avoid runs $a_i+a_{i+1}+\cdots+a_j$ that add to zero (where $1<i<j\le k$).

In the case when $k=n-1$ this is known -- it is covered by the theory of sequenceable and $R$-sequenceable groups. Has anyone looked at the above generalisation before? Even though $k=n-1$ feels like it should be the hardest case, it doesn't seem to imply the other cases. I have some hope of a proof for the case when $n$ is prime, but before I go to the effort of sorting out the details I want to be sure I'm not reinventing the wheel.

It is tempting to think the problem will be easy when $k$ is very much smaller than $n$. However, it is possible that $S$ might be all the nonzero elements of some subgroup of $\mathbb{Z}_n$, in which case you are just looking for a sequencing of that subgroup. This will exist, but are probably very rare in some sense.

This problem was told to me by Jeff Dinitz, and I think he might have got it from Dan Archdeacon. Any pointers to relevant literature will be much appreciated.

share|improve this question
1  
I don't know if this has been studied before, but some relevant problems, most of which probably you are aware of: openproblemgarden.org/op/snevilys_conjecture, mathoverflow.net/questions/24108/…, cs.elte.hu/blobs/diplomamunkak/msc_mat/2013/… –  domotorp Apr 25 at 4:12
    
I can confirm the Dan Archdeacon link. He told me this problem a few months ago. (seems tough to me) –  Peter Dukes Apr 28 at 7:34

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.