# A Pascal's-triangle -like random process

I was exploring Pascal's triangle on a cylinder when I encountered this puzzle-like problem. It is surely elementary, but perhaps weekend-entertaining.

Start with a permutation of $(1,2,3, \ldots, n)$, call it $(x_1,x_2,x_3,\ldots,x_n)$. Perform two operations in sequence: Sum, and Shuffle. Sum computes a new sequence $x'_i = (x_i + x_{i+1})$, with cylindrical index wraparound. (This is the Pascal's-triangle aspect.) Shuffle permutes the resulting numbers (below I used a random permutation). Then the Sum/Shuffle-transformations are repeated. Here is an example, for $n=4$:

I hope the process is clear without further formal definitions. The numbers in the sequence grow by powers of 2, but approach the same normalized ratio, and so in that sense "approach" equality. One could ask many questions (I'll resist, although I welcome speculation!), but this is perhaps the primary question:

For which $n$ could the described process lead to a sequence of identical numbers?

For $n=2$, $(1,2)$ is the only option, which ends in $(3,3)$ after just one step. For $n=3$, all starting permutations lead to a permutation of $(3,4,5)$, which leads to a permutation of $(7,8,9)$, which leads to a permutation of $(15,16,17)$, and then to $(31,32,33)$, and so on. This is all I know: $n=2$ must end in a constant sequence, $n=3$ cannot, and $n=4$ might.

Addendum. After Douglas Zare's (nice!) analysis answered the question for all but $n = 0 \mod 4$, I concentrated on $n=8$ and found these two examples: $$\left( \begin{array}{cccccccc} 7 & 2 & 8 & 1 & 5 & 4 & 6 & 3 \\ 10 & 9 & 10 & 9 & 6 & 9 & 10 & 9 \\ 9 & 6 & 9 & 10 & 9 & 10 & 9 & 10 \\ 15 & 15 & 19 & 19 & 19 & 19 & 19 & 19 \\ 19 & 19 & 15 & 19 & 19 & 19 & 19 & 15 \\ 34 & 38 & 34 & 34 & 38 & 38 & 38 & 34 \\ 34 & 38 & 34 & 38 & 34 & 38 & 34 & 38 \\ 72 & 72 & 72 & 72 & 72 & 72 & 72 & 72 \end{array} \right)$$

$$\left( \begin{array}{cccccccc} 4 & 3 & 6 & 1 & 8 & 7 & 2 & 5 \\ 9 & 7 & 9 & 7 & 9 & 15 & 9 & 7 \\ 9 & 7 & 9 & 15 & 9 & 7 & 9 & 7 \\ 16 & 16 & 24 & 24 & 16 & 16 & 16 & 16 \\ 24 & 16 & 16 & 16 & 24 & 16 & 16 & 16 \\ 40 & 40 & 32 & 32 & 40 & 40 & 32 & 32 \\ 40 & 32 & 40 & 32 & 40 & 32 & 40 & 32 \\ 72 & 72 & 72 & 72 & 72 & 72 & 72 & 72 \end{array} \right)$$ The rows alternate between permutation and sum, i.e., each odd row is a permutation of the even row above.

-
Do you know of examples where it can never lead to a sequence of identical numbers? Or is it possible that it could happen for any $n$? –  Vaughn Climenhaga May 27 '11 at 19:51
@Vaughn: I don't understand how it behaves. I have only found it leading to a constant sequence for $n=4$, but my (limited) theoretical explorations have led nowhere. –  Joseph O'Rourke May 27 '11 at 19:56
If you're allowed to permute randomly then for $n=4$ you can stop the sequence from becoming constant by arranging that it's always "odd,odd,even,even". On the other hand it's obvious that for any $n$ you can get to a sequence of identical numbers because, for example, you can start with a sequence of identical numbers. –  Kevin Buzzard May 27 '11 at 21:02
The only way to get to a constant state from one which is not constant is if the predecessor alternates between two values, which is impossible for $n$ odd. –  Douglas Zare May 27 '11 at 23:58
@domotorp: For $n=6$, $(5,6,1,4,3,2)$ becomes $(7,11,7,5,7,5)$. So at least achieving the same sequence mod 2 is not equivalent. But the parity behavior is quite interesting... –  Joseph O'Rourke May 28 '11 at 20:35

Not a complete answer, but for $n=4$ if you start with an arithmetic progression ($1,2,3,4$ works) then you have probability $1$ of ending up with them all being identical.

Consider the following set of states for the quadruple $(x_1,x_2,x_3,x_4)$ once it has been ordered so that $x_1 \leq x_2 \leq x_3 \leq x_4$:

State $A_0$: All the $x_i$ are equal.

State $A_1$: $\vec x$ is of the form $(a-d,a-d,a+d,a+d)$ for some $a,d$.

State $A_2$: $\vec x$ is of the form $(a-d, a, a, a+d)$ for some $a,d$.

State $A_3$: the four numbers are distinct and form an arithmetic progression, so $\vec x = (a - 3d, a-d, a+d, a+2d)$ where $a$ is the average value.

Given $\vec x$ in one of the four states, choose a permutation from $S_4$ at random and apply the procedure described in the question. There are really only $3$ equivalence classes of permutations, since you only need to know which of the three numbers $x_2,x_3,x_4$ does not get added to $x_1$, and then everything else is determined.

It's not hard to show that if you are in state $A_j$, then with probability $1/3$ you remain in state $A_j$, while with probability $2/3$ you move to state $A_{j-1}$. (Of course if you're in state $A_0$ then you stay there no matter what.) This means that almost surely you eventually end up in $A_0$, where all four numbers are equal.

I'm not sure what happens if you try this for $n\geq 5$.

-
Nice, Vaughn! This all seems right to me... –  Joseph O'Rourke May 27 '11 at 21:59

This covers all but multiples of $4$:

Consider the preimage of the $0$ vector under the cyclic sum. All vectors in the preimage alternate $(a,-a,...,a,-a)$ and if the length is odd, then $a=-a$. By invariance under affine transforms, the preimages of constant vectors are shifted by a constant. So, if $n\gt 1$ is odd, you don't reach a constant vector since you don't start with one.

For $n==2k$, what is the preimage of a vector $\vec{v} = (v_1,...v_n)$ with $k$ $0s$ and $k$ $1s$? Up to a cyclic shift, the vectors whose cyclic sum is $\vec{v}$ are $(a,-a,a,-a...)+(0,v_1,v_2-v_1,v_3-v_2+v_1,...\sum_{j=1}^i (-1)^{i-j}v_j,...)$ and $0=\sum_{j=1}^n(-1)^{n-j}v_j$. If $k$ is odd, then no way to choose signs for the $1s$ will make that sum $0$, since you can't have equally many $+1$s and $-1$s. So, if $n\gt 2$ is congruent to $2 \mod 4$ then you don't reach a constant vector since you can't reach a vector with only two values, with $n/2$ of each.

It's not obvious to me how this might be extended to the next preimages since the preimages of balanced $0-1$ vectors do not need to have only a few values.

On the flip side, if there is a way to go from any vector to a constant vector, then this will happen eventually with probability $1$. I don't yet see whether this is possible for $n=8$.

-
This is suggestive of the proof that (real) Hadamard matrices must have order 4k if the order is large enough. Perhaps there is more of a connection? Gerhard "Ask Me About System Design" Paseman, 2011.05.27 –  Gerhard Paseman May 28 '11 at 1:24

It is possible if and only if 4 divides n. Douglas Zare showed that if 4 does not divide n, then it is impossible (btw, his argument might be simpler to state mod 2 - if 4 does not divide n, then it is already impossible to get all numbers divisible by 4). Now, if n=4k, do the following:

1, 12, 2, 10, 4, 8, 6, 7, 5, 9, 3, 11.

This will give 2k-1 n's, 2k-1 n+2's and two n+1's. Next, do

12, 14, 12, 14, 12, 14, 12, 14, 12, 14, 13, 13.

This gives 4k-2 2n+2's, one 2n+3 and one 2n+1.

Now, for simplicity, subtract 2n+2 from each number. We have all zeros but one +1 and one -1. Make the permutation so that we double the number of +1's and -1's in each step, until they become >n/4, then "mix them a bit"* so that in the next step we can exactly n/2 of both. Then an alternating sequence will give all equal numbers.

$^*Edit$: As Douglas pointed out this mixing is not that clear how to do. So instead, I claim that we for any i from 1 to n/2 it is possible to get exactly i +1's and i -1's. The proof is by induction - we either double or double -1, by putting a +1 and a -1 next to each other. Eventually we can get n/2 of each and we are done.

However, this my method only works for the numbers 1, 2, .. , n. What if we start from another sequence? Mod 2 the problem is always solvable, maybe that helps, but over Z already 1, 0, .. , 0 is not clear how to solve.

Edit: As Doublas pointed out this is possible if and only if n is a power of 2. So to summarize, I think if 4 does not divide n>1, then you can not get all equal numbers starting from 1, 2, .. , n, if 4 divides n you can, while if is n>2 is a power of 2, then it seems you can start from any sequence. (Though we have not seen a full proof of this last part yet.)

-
What do you mean by "then mix them a bit?" –  Douglas Zare May 29 '11 at 13:58
You are right, I fixed it. (Hopefully well...) –  domotorp May 29 '11 at 16:05
I think you have to aim for $n/4$ $1$s and $-1$s with $n/2$ $0$s, and then go from that to $n/2$ of each. So, for example, with $n=12$, you go from $1\to 2 \to 3 \to 6 \to 0$ $1$s and $-1$s. The step from $2 \to 3$ can be done as $0101(-1)0(-1)00000$. I don't think $4\to 6$ is possible. –  Douglas Zare May 30 '11 at 3:39
Also, it's impossible to go from $100000...0$ to a constant sequence except possibly when $n$ is a power of $2$ since no odd prime will divide the sum of the values, $2^k$ after $k$ cyclic sums, but a constant vector would be divisible by $n$. –  Douglas Zare May 30 '11 at 3:43
Since you can't reach a constant vector from $10...0$ (with $n=12$), you also can't reach a constant vector from $k0...0$ for any $k$, even with $k$ divisible by $3$ or $12$. What I asked before was whether there is a way to get stuck if you start from a permutation and make some bad choices. –  Douglas Zare Jun 2 '11 at 10:37
The basic structure of the numbers you get is invariant under affine transformations, from $(a,b,c,d)$ to $(ra+u,rb+u,rc+u,rd+u)$, so you may as well assume you're working with integers that sum to 0 --- i.e., $d=-(a+b+c)$. (It doesn't really matter that they're integers, but it's convenient.) After the first sum, you're at a 4-tuple of the form $(A,B,-A,-B)$. A permutation either brings the $A$ and $-A$ together (cyclically), or it doesn't. If it doesn't, the next sum remains of the form $(A,B,-A,-B)$ (with new values of $A$ and $B$), so the process continues. If it does bring the $A$ and $-A$ together, say to $(A,-A,B,-B)$, the next sum has the form $(0,C,0,-C)$, which can be scaled to $(0,1,0,-1)$, unless $C=0$ --- i.e., unless $A=B$. If the next permutation brings the 0's together (cyclically), the ensuing sum remains $(0,1,0,-1)$. If it leaves them apart, the ensuing sum is $(1,1,-1,-1)$, so you're back at something of the form $(A,B,-A,-B)$, but this time with $A=B$ --- i.e., the condition under which you can get to $(0,C,0,-C)$ with $C=0$.