[SeqFan] Re: Suggestion for a sequence: weights on a circle

[Antti Karttunen]

Cheers,

this old thread inspired me to ask new questions. (After these quotes):

Brendan McKay wrote September 11 2005:

>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.
>
>  
>
Brendan McKay wrote Sep 14 2005:

>Edwin has produced strong evidence that there are no solutions when
>n is a prime power.  I can't prove that, but it is easy to show that
>there are solutions when n is not a prime power.  Every such number
>can be written as m*n where m,n are coprime.  Now continue like in 
>this example (n=5,m=3):
>
>    Write a permutation of {1,2,...,n} m times:
>       5  1  3  4  2  5  1  3  4  2  5  1  3  4  2
>    Add 0,n,2n,...,(m-1)n,0,... cyclically:
>       5  6 13  4  7 15  1  8 14  2 10 11  3  9 12
>    That's a solution.
>
>  
>
That's nice. If you stack two balanced circles on the top of each 
another, it's still balanced.

>    Hugo's example for n=15 suggests another way to do the last step:
>    Replace the value v in position i by m*v+(i mod m).
>
>Brendan.
>
>  
>

T. D. Noe wrote Sep 14 2005:

>This problem is similar to the following:
>
>For which n is there an equiangular polygon whose sides are some
>permutation of 1,2,3,...,n.  The smallest solution is n=6, for which there
>are essentially 4 permutations: (1,4,5,2,3,6), (1,5,3,4,2,6),
>(1,6,2,4,3,5), and (1,6,3,2,5,4).
>
>The problem was given on page 10 of the latest issue of MuddMath.  See
>http://www.math.hmc.edu/muddmath/
>
>  
>
>Tony
>
>  
>
More exactly, it's "Bernoff's Puzzler" on the page 12/20 of the 
following PDF-file:
http://www.math.hmc.edu/muddmath/v4n1.pdf
(or page 10/18 of the original).
And the problem is not just similar to New Scientist's puzzle.
It's exactly the _same_ problem, just in a bit different guise.

 From the wording used in the Bernoff's puzzle:
"Extra Credit: Determine all values of N for which this is possible."
hints that there should be a solution other than just a brute computer 
search.

Also, does anybody have access to the next issue of New Scientist 
(September, October XXX 2005?)
where the answer to the original question can be found?

Hugo Pfoertner wrote Sep 14 2005:

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

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

The above sequence is still not in OEIS, by the way. In above sequence 
Hugo seems to
have discarded the reflections mirrored over the X-axis (or the 
real-axis if we think in the
terms of roots of unity), so maybe we need another sequence which gives 
also them.
(*2 of the above one, there are no symmetrical solutions because all the 
weights are different...)

But when I started thinking how to compute this (or similar) sequences 
by brute generate-and-test
method, and how to do that without floating point arithmetic, I found 
another interesting problem.
Continued in the next message...


Yours,

Antti Karttunen