6
$\begingroup$

I have a task:
Find all $n\ \epsilon \ N, \ n > 1$ for which a permutation $a_1,\ a_2,\ ...,\ an\ $ of numbers $ 0,1, ..., n - 1$ exists such that $a_1,\ a_1+a_2,\ ...,\ a_1+a_2+\ ...\ +an\ $ form a CRS $mod\ n$.

So far I've come to the conclusion that $a_1$ must be $0$ because otherwise there would be two equal numbers from the listed above (so it won't be a CRS) and I think that odd numbers don't form CRS because $n*(n-1)/2 \ \ (mod\ n)$ is also $0$ so again won't form CRS. My assumption is that all even numbers can form CRS and satisfy the conditions above since I have found such permutations for numbers 2,4,6,8, but I don't know how to prove it and if it is right at all.

Would appreciate some help: first - whether I have made any mistakes so far, and second - with proof if I am right.

Thanks in advance!

$\endgroup$
  • $\begingroup$ You say that odd numbers don't work but prime numbers do work...? $\endgroup$ – Greg Martin Jul 17 '17 at 23:29
  • $\begingroup$ Sorry, meant to say even $\endgroup$ – vixenn Jul 18 '17 at 18:44
11
$\begingroup$

Your question is about sequenceable groups, introduced in 1961 by Basil Gordon.

A finite group is called sequenceable if its elements can be written as a sequence $(g_1,g_2,\dotsc,g_n)$ so that all the partial products $g_1,g_1g_2,\dotsc,g_1g_2\dotsb g_n$ are pairwise distinct. Gordon has shown that a finite abelian group is sequenceable if and only if it contains exactly one involution (element of order $2$). It is easily seen that this condition is necessary, and Gordon proved that it is also sufficient.

A great review of this subject can be found in this paper by Matt Ollis; see also more recent papers by the same author, such as this one.

$\endgroup$
  • $\begingroup$ Thank you for the materials! I've seen similar problem, with products and not sums, but I don't understand it well enough to be able to apply it to my problem with the sums. $\endgroup$ – vixenn Jul 18 '17 at 20:49
  • 1
    $\begingroup$ @vixenn: Seva completely answered your question (his product is your sum), so I suggest that you accept his answer officially (so that it turns green). $\endgroup$ – GH from MO Jul 19 '17 at 10:03
  • $\begingroup$ Reading the materials a little bit more thoroughly, I think I understand it better now. Thanks for the help, @Seva :) $\endgroup$ – vixenn Jul 19 '17 at 20:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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