[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