[seqfan] Re: Permutations Of +- Integers

franktaw at netscape.net franktaw at netscape.net
Sat Apr 25 02:15:31 CEST 2009


OK, here's a correct proof.

First, a lemma:

Any 4k consecutive integers can be given signs so that their sum is 
zero.
Let a be the first of the integers; pair them in opposites, so that 
each pair sums to 2a + 4k - 1.  There are then 2k such pairs: give half 
of them a positive sign, and the other half negative.  The sum will 
then be zero.

Now the proof:

Look a n modulo 4.  If n = 0 (mod 4), the lemma immediately leads to 
the proof, duplicating the original 0 sum.
If n = 3 (mod 4), we can take +1, +2, -3, and the other numbers can be 
made tol sum to zero by the lemma.
If n = 1 (mod 4), the argument below shows that the first number in any 
counterexample must be n.  The number of remaining numbers, consecutive 
from 1, is a multiple of 4, so we can duplicate n as a sum.
And if n = 2 (mod 4), the argument below shows that the first two 
numbers in any counterexample must be n,1.  There are then a multiple 
of 4 consecutive integers (from 2) remaining, so setting their sum to 
0, we duplicate n-1.
Q.E.D.

Franklin T. Adams-Watters

-----Original Message-----
From: franktaw at netscape.net

Sorry, there's a mistake here.  At the last step, we can get to n-2 by
getting to |Q(m-1)| = 1, and r(m) = n-1.  And in fact, the permutation
4,1,2,3 gets Q values of 0,4,3,1,-2 when we do this.  Of course, this
isn't a counterexample to the claim; we can instead get Q values
0,4,3,1,4, which duplicates the 4.  I'm pretty sure the result is
correct; I'll see if I can patch the proof.

-----Original Message-----
From: franktaw at netscape.net

It's a(1) = 1, a(2) = 1, and the rest zeros.

Consider the assignment of signs which minimizes the absolute value of
the sum at each point (if two values with the same absolute value are
possible, we don't care which is taken).  The absolute sum must then be
0 <= |Q(m)| <= n; this can fail to duplicate only if it takes on all
n+1 possible values.  But |Q(m)| = n with this assignment is possible
only when Q(m-1) = 0 and r(m) = n.  If m != 1, this is a duplication of
the value 0, so we must have r(1) = n.  Now the only ways to get |Q(m)|
= n-1 is for r(2) = 1, or some r(m) = n-1 and Q(m-1) = 0; but the
latter again duplicates the 0 sum.  Repeating this argument, we can't
set r(2) = 1 to immediately get |Q(2)| = n-2, because 1 has already
been used.  So the n-2 must follow a 0, and we have a duplication.

Franklin T. Adams-Watters


-----Original Message-----
From: Leroy Quet <q1qq2qqq3qqqq at yahoo.com>

This question is inspired by the game at:
http://gamesconceived.blogspot.com/2009/04/permutations-of-integers.html

Take the permutation, R= (r(1),r(2),r(3),...,r(n)), of (1,2,3,...,n).
Then give
a sign (+ or -) to each integer of the permutation to get
(q(1),q(2),q(3),...q(n)).
(In other words, each q(m) = + or - r(m).)
Let
Q(m) = sum{k=1 to m} q(k), for each m where 0 <= m <= n.
(Q(0) = 0.)

How many permutations R are such that, no matter how the signs are
assigned to
the integers of the permutation, then no |Q(m)| equals any |Q(j)|, for
each j
and m where 0 <= j < m <= n?

Is the sequence of the number of such permutations of (1,2,3,..,n)
easily derived, or even trivially derived?




More information about the SeqFan mailing list