Suggestion for a sequence: weights on a circle

[Edwin Clark]

On Wed, 14 Sep 2005, Hugo Pfoertner wrote:

> Brendan McKay wrote:
> > 
> > A recent puzzle in New Scientist suggests the following.
> > 
> > Suppose you have n objects, with weights 1,2,3,...,n.
> > (That is, exactly one object with each of those weights.)
> > 
> > How many ways are there to place these objects evenly spaced
> > around the circumference of a disk so that the disk will
> > exactly balance on the centre point?
> > 
> > In algebraic terms, how many permutations p1,p2,...,pn
> > are such that the polynomial p1 + p2*x + ... + pn*x^(n-1)
> > has exp(2 pi i/n) as a zero?
> > 
> > An example for n=10 is [2, 9, 1, 8, 5, 7, 4, 6, 3, 10]. I don't even
> > know which n have a solution. Certainly not n=1,2,3,4. For n=10
> > there are 480 solutions, or 48 equivalence classes if "1" is placed
> > in a fixed position, or 24 equivalence classes if the mirror
> > image is regarded as the same.
> > 
> > Brendan.
> 
> I've written a program
> http://www.randomwalk.de/sequences/balcir.for
> (calling my lexicographic permutation function
> http://www.randomwalk.de/sequences/lpg.txt)
> to get the first few terms of this sequence. I keep the mass 1 fixed at
> (1,0) on the unit circle.
> The smallest n for which a solution exists is n=6 with 4 solutions
>   Count       Mass
>         1  2  3  4  5  6
>         at  positions
>      1  1  4  5  2  3  6
>      2  1  5  3  4  2  6
>      3  1  6  2  4  3  5
>      4  1  6  3  2  5  4
> 
> No solutions for n=7,8,9,
> 
> 48 solutions (as indicated above) for n=10. The lexicographically first
> solution is:
>  [1  4  5  8  9  2  3  6  7 10]
> the others can be found at
> http://www.randomwalk.de/sequences/balcir10.txt
> 
> No solution for n=11.
> 
> 1464 solutions for n=12. Lexicographically first:
> [1  2  6 10  8  9  4  5  3  7 11 12]
> List: http://www.randomwalk.de/sequences/balcir12.txt
> 
> No solution for n=13.
> 
> 1440 solutions for n=14. Lexicographically first:
> [1  4  5  8  9 12 13  2  3  6  7 10 11 14]
> List: http://www.randomwalk.de/sequences/balcir14.txt
> 
> 96 solutions for n=15. Lexicographically first:
> [1  5  9 10 14  3  4  8 12 13  2  6  7 11 15]
> List: http://www.randomwalk.de/sequences/balcir15.txt
> 
> n=16 seems doable, but will take a few days CPU.
> 
> The suggested sequence (number of ways to arrange the weights) would
> start (first term n=1)
> 
> 0 0 0 0 0 4 0 0 0 48 0 1464 0 1440 96
> 
> Hugo Pfoertner
> 



I conjecture that there are no solutions if n is a prime power.
I have verified this via Maple up to n = 500  using the following idea.
One can probably use this idea to prove this conjecture. I'm just too 
lazy. 
For this part it suffices to show that if n is a prime power then no 
integral polynomial of degree n-1 with n distinct coefficients has a 
primitive nth root of unity as a root. That is, such a polynomial is 
not divisible by the nth cyclotomic polynomial. For n a prime power 
these are easy to find. Here's a Maple program illustrating no 
solution for n = 16:

> with(numtheory):

> for n from 16 to 16 do
> c:=cyclotomic(n,x);
> k:=degree(c,x);
> m:=n-k;
> f:=add(a[i]*x^(i-1),i=1..m);
> p:=sort(collect(expand(f*c),x));  We just need to show that p has less 
than n distinct coefficients.
> S:={coeffs(p,x)};
> nops(S);
> od;

                                   8
                             c := x  + 1


                                k := 8


                                m := 8


                        2         3         4         5
  f := a[1] + x a[2] + x  a[3] + x  a[4] + x  a[5] + x  a[6]

            6         7
         + x  a[7] + x  a[8]


        15         14         13         12         11
  p := x   a[8] + x   a[7] + x   a[6] + x   a[5] + x   a[4]

            10         9         8         7         6         5
         + x   a[3] + x  a[2] + x  a[1] + x  a[8] + x  a[7] + x  a[6]

            4         3         2
         + x  a[5] + x  a[4] + x  a[3] + x a[2] + a[1]


        S := {a[8], a[7], a[6], a[5], a[1], a[2], a[3], a[4]}


                                  8