Wednesday, April 22, 2009

Permutations Of +- Integers

This is a game for two players, player 1 and player 2.

There are two lists of numbers being maintained, list A and list B.

Both lists start the game without any integers.

On move number n*, player 1 picks the sign (+ or -) for the integer, which has an absolute value of n, for list B.
And on move number n, player 2 picks the sign (+ or -) for the integer, which has an absolute value of n, for list A.

Then player 1 puts the integer (+ or - n), which had its sign picked by player 2, somewhere among the integers already in list A: either between integers already there, or at the beginning or end of the list of integers.
Then player 2 puts the integer (+ or - n), which had its sign picked by player 1, somewhere among the integers already in list B.

So, the each list, on move n, is a permutation of the integers
(+-1,+-2,+-3,...,+-n). On the nth move, the integers +-1, +-2, +-3,...+-(n-1) each remain in the same order relative to each other, but the +-n is inserted somewhere in each list.

*(A move consists of a series of steps, these being: Each player picking a sign for an integer, then each player placing an integer in a list.)

After a predetermined number of moves, the game is over. (Let the number of total moves be the positive integer m.)

Scoring is as follows:
Say, list A is the permutation (a(1),a(2),a(3),..,a(m)) of (+-1,+-2,+-3,...,+-m).
Let A(n) = sum{k=1 to n}a(k) be a partial sum of the first n terms of the permutation which is list A.
Player 2 (note: player 2) gets a point for every distinct k where |A(k)| = at least one |A(j)|, for 1<= j < k <= m, or where A(k) = 0.

Say, list B is the permutation (b(1),b(2),b(3),..,b(m)) of (+-1,+-2,+-3,...,+-m).
Let B(n) = sum{k=1 to n}b(k) be a partial sum of the first n terms of the permutation which is list B.
Player 1 (note: player 1) gets a point for every distinct k where |B(k)| = at least one |B(j)|, for 1<= j < k <= m, or where B(k) = 0.

Math question: How does the integer sequence {c(k)} start where c(n) = the number of permutations of (+ or - 1, + or - 2, + or - 3,...,+ or - n), where no partial sum of the first k terms of the sequence, 1 <= k <= n, equals any partial sum of the first j terms of the sequence, for all k and j where 0<= j < k <=n, no matter what the signs of the integers are?
(What are the permutations that gain 0 points for the player picking the signs, no matter how they pick the signs?)

Thanks,
Leroy Quet

No comments: