Generalization of "BMO2 2001 Question 1 Recurrence Relation"

Question

In this question, a process is proposed. I am going to propose an extension of the process to more players, then ask the same question:

$k$ players sit in a circle, with player $i$ starting with $p_i$ beans. At a player's turn, he gives to each other player exactly enough beans to double the other player's stash.

After $nk$ turns (so we've gone around the circle $n$ times,) what are the conditions for the state to be $(p_k,p_{k-1},\dots,p_1)$ - that is, for the totals for the players to be reversed?

Via numerical experimentation, it looks like the answer is:

$$p_i = 2^{(n+1)k-i} + 2^{i-1}$$

(Since the question is homogeneous, you can obviously start with any multiple of that vector.)

So with $k=5$ players and $n=2$ rounds, you get:

$$\begin{align}(16385,8194,4100,2056,1040) &\to(995,16388,8200,4112,2080)\\ &\to(1990,1001,16400,8224,4160)\\ &\to(3980,2002,1025,16448,8320)\\ &\to(7960,4004,2050,1121,16640)\\ &\to(15920,8008,4100,2242,1505)\\ &\to(65,16016,8200,4484,3010)\\ &\to(130,257,16400,8968,6020)\\ &\to(260,514,1025,17936,12040)\\ &\to(520,1028,2050,4097,24080)\\ &\to(1040,2056,4100,8194,16385) \end{align} $$

For $n=4$, $k=3$, you get:

$$\begin{align}(16385,8194,4100) &\to(4091,16388,8200) &\to(8182,4097,16400) &\to(16364,8194,4121) \\ &\to(4049,16388,8242) &\to(8098,4097,16484) &\to(16196,8194,4289) \\ &\to(3713,16388,8578) &\to(7426,4097,17156) &\to(14852,8194,5633) \\ &\to(1025,16388,11266) &\to(2050,4097,22532) &\to(4100,8194,16385) \end{align} $$

Note those two answers start at the same value, which, if this conjecture is right, will always be the case if $(n_1+1)k_1=(n_2+1)k_2.$

Seems like there should be something relatively simple going on here, but I'm not seeing it.

Note that after $k$ terms, if $T=\sum p_i$ (which is constant as the game evolves) then:

$$(p_1,\dots,p_k)\xrightarrow{k\text{ turns}} (2^kp_1-2^{k-1}T, 2^kp_2-2^{k-2}T,\dots,2^kp_k-2^{0}T)$$

That's likely to be strongly related.

Answer 1

An equivalent version of the process about is to first have player $1$ double everybody's values, then have everybody hand their pile counter-clockwise - $2$ passes his pile to $1$, $3$ to $2,\dots,$ and $1$ to player $k$. Then repeat, with player $1$ always giving from the pile in front of him. After $k$ turns, this is identical to $k$ turns of the original process, but this new game is homogenous - each turn is identical as a linear map. Given a starting vector $\mathbf p=(p_1,p_2,\dots,p_k)^T$ for the game, the result of a single turn can be written as:

$$PS\mathbf p$$

Where $$S=\begin{pmatrix} 1&-1&-1&\dots&-1\\ 0&2&0&\dots&0\\ 0&0&2&\dots&0\\ & & &\dots&\\ 0&0&0&\dots&2 \end{pmatrix} = 2I -\begin{pmatrix} 1&1&1&\dots&1\\ 0&0&0&\dots&0\\ 0&0&0&\dots&0\\ & & &\dots&\\ 0&0&0&\dots&0 \end{pmatrix}$$

And $P$ is the rotation matrix: $$P=\begin{pmatrix}0&1&0&\dots&0\\ 0&0&1&\dots&0\\ & & &\dots&\\ 0&0&0&\dots&1\\ 1&0&0&\dots&0 \end{pmatrix}$$

After $k$ turns (or one round) of of our initial game, we are at the same state as after $k$ turns of this different game, namely $(PS)^k\mathbf p$.

Now, $P$ and $S$ both send elements of the $n-1$ dimensional subspace $V=\{(x_i)\in \mathbb R^k\mid \sum x_i=0\}$ to other elements of $V$, which is easily verified, and is a result of the fact that the total number of beans is an invariant of the game.

There is also an eigenvector $\mathbf v=(2^{k-1},2^{k-2},\dots,2^0)^T$ of $PS$ with eigenvalue $1$.

Finally, given $\mathbf x\in V$, we see that $(PS)\mathbf x = 2(x_2,x_3,\dots,x_k,x_1)^T=2P\mathbf x$, and thus $(PS)^kx = 2^k\mathbf x$. So every element of $V$ is an eigenvector of $(PS)^k$ for eigenvalue $2^k$.

Now, letting $\tau=\sum p_1$, we can see that $\mathbf p-\frac{\tau}{2^k-1}\mathbf v\in V$, so we have after $n$ rounds:

$$(PS)^{nk}\mathbf p = \frac{\tau}{2^k-1}\mathbf v+ 2^{nk}\left(\mathbf p-\frac{\tau}{2^k-1}\mathbf v\right)=2^{k}\mathbf p -\tau \frac{2^{nk}-1}{2^k-1}\mathbf v$$

Now, if $(PS)^{nk}$ send $(p_1,p_2,\dots,p_k)^T\mapsto(p_k,\dots,p_1)^T$, then the reverse game, in $n$ rounds, where player $k$ starts and the rotation happens in reverse, must send $(p_k,\dots,p_1)^T\mapsto (p_1,p_2,\dots,p_k)^T$.

The reverse game turn can be written as $SP^{-1}$ - we shift the beans counter-clockwise, then player $1$ doubles everybody. So $n$ rounds of this is $(SP^{-1})^{nk}$. This matrix has the same eigenspace $V$ for eigenvalue $2^{nk}$, but has eigenvector $\mathbf v'=(1,2,\dots,2^{k-1})^T$ for eigenvalue $1$. So we get:

$$\begin{align}\mathbf p &= (SP^{-1})^{nk}(PS)^{nk}\mathbf p\\ &=(SP^{-1})^{nk}\left(2^{nk}\mathbf p - \frac{2^{nk}-1}{2^k-1}\tau \mathbf v\right)\\ &=2^{2nk}\mathbf p - 2^{nk}\frac{2^{nk}-1}{2^k-1}\tau \mathbf v - \frac{2^{nk}-1}{2^k-1}\tau \mathbf v' \end{align}$$

Solving for $\mathbf p$, that gives us:

$$\mathbf p =\frac{\tau}{(2^k-1)(2^{nk}+1)}\left(2^{nk}\mathbf v+\mathbf v'\right)$$

Since the problem is homogenous, we can just choose $\tau=(2^{nk}+1)(2^k-1$, and we get:

$$\mathbf p = 2^{nk}\mathbf v+\mathbf v'$$

Note that we can compute the totals of the vector on the right as the $\tau$ we chose.

So this $\mathbf p$ is the only possible solution.

We can check, using that fact that $\mathbf v'-\mathbf v\in V$: $$(PS)^{nk} (2^{nk}\mathbf v+\mathbf v') = (2^{nk}+1)\mathbf v + 2^{nk}(\mathbf v'-\mathbf v)= \mathbf v + 2^{nk}\mathbf v'$$ Since $\mathbf v$ and $\mathbf v'$ are reverses of each other, this means that $(PS)^{nk}\mathbf p$ is the reverse of $\mathbf p$, and we are done.

Here's an entirely general result. Given a permutation $\sigma$ of $\{1,\dots,k\}$, let $P_\sigma$ be the permutation matrix, and you want a starting position $\mathbf p = (p_1,\dots,p_k)^T$ after $k$ rounds to go to $P_{\sigma}\mathbf p$ then $$\mathbf p=\left(2^{nk}I-P_\sigma\right)^{-1}\left(2^{k-1},\dots,2^{0}\right)^T$$

For example, if $n=1,k=5$ we can start $$(180747,91542,45848,25388,16912 )$$ and, in one round (five turns,) we get $$(16912,45848,25388,91542,180747).$$ This swaps the ends and rotates the inner $3$.

When $\sigma^2=1$, we have that $\left(2^{nk}I-P_\sigma\right)^{-1}$ is a rational mutiple of $2^{nk}I+P_{\sigma}$. So we can use $$p_i = 2^{nk+(k-i)}+2^{k-\sigma(i)}$$

When $\sigma(i)=k+1-i$, our original question, we get our original result.

For the more general $\sigma$ with $\sigma^d=1$, we have that:

$$\left(2^{nk}-P_\sigma\right)^{-1} = \alpha\left(\sum_{j=0}^{d-1}2^{nkj}P_{\sigma^{d-1-j}}\right)$$

for some rational $\alpha$.

So we can see that each $$p_i = \sum_{j=0}^{d-1} 2^{nkj+k-\sigma^{-(1+j)}(i)}$$

This means that each $p_i$ is a sum of $d$ distinct powers of $2$, and no power of $2$ contributes to different $p_i$ - that is, they are bitwise disjoint. The powers with exponent $nk\alpha + k-\beta$ with $\alpha=0,\dots,d-1$ and $\beta=1,\dots,k$ goes into $p_{\sigma^{\alpha+1}(\beta)}$.

Answer 2

I got the same results as the OP, but I arrived at them differently. So I go to the point where we got the same equations and then I stop.

For the case $k = 4$.

If your current state is $P$

Then your state after the first player takes his turn is

$S_1 P =\begin{pmatrix} -1 & -1 & -1 & 1\\ 0 & 2 & 0 & 0\\ 0 & 0 & 2 & 0\\ 0 & 0 & 0 & 2\\ \end{pmatrix} P$

Your state after the second player takes his turn is

$S_2 P =\begin{pmatrix} 2 & 0 & 0 & 0\\ -1 & 1 & -1 & -1\\ 0 & 0 & 2 & 0\\ 0 & 0 & 0 & 2\\ \end{pmatrix} P$

Your state after the third player takes his turn is

$S_3 P =\begin{pmatrix} 2 & 0 & 0 & 0\\ 0 & 2 & 0 & 0\\ -1 & -1 & 1 & -1\\ 0 & 0 & 0 & 2\\ \end{pmatrix} P$

And your state after the fourth player takes his turn is

$S_4 P =\begin{pmatrix} 2 & 0 & 0 & 0\\ 0 & 2 & 0 & 0\\ 0 & 0 & 2 & 0\\ -1 & -1 & -1 & 1\\ \end{pmatrix} P$

The state-change matrix after one round would be $M = S_4 \cdot S_3 \cdot S_2 \cdot S_1 \cdot=\begin{pmatrix} 8 & -8 & -8 & -8\\ -4 & 12 & -4 & -4\\ -2 & -2 & 14 & -2\\ -1 & -1 & -1 & 15\\ \end{pmatrix}$

So the state after n rounds would be $M^n \cdot P$, and we need to solve

$M^n \begin{pmatrix}a\\ b\\ c\\ d \end{pmatrix} = \begin{pmatrix}d\\ c\\ b\\ a \end{pmatrix}$

We find

$M \begin{pmatrix}43\\ 22\\ 12\\ 8 \end{pmatrix} = \begin{pmatrix}8\\ 12\\ 22\\ 43 \end{pmatrix}$

$M^2 \begin{pmatrix}683\\ 342\\ 172\\ 88 \end{pmatrix} = \begin{pmatrix}88\\ 172\\ 342\\ 683\end{pmatrix}$

$M^3 \begin{pmatrix} 10923\\ 5462\\ 2732\\ 1368\end{pmatrix} = \begin{pmatrix} 1368\\ 2732\\ 5462\\ 10923\end{pmatrix}$

---

From here on, we count everything starting at $1$. If there is an initial state, it's index is $0$. Lets define

$r_i \in \mathbb R^{k \times k} = $ the matrix that is all zeros except that the ith row is all ones.

$\quad$ Note that $\forall 1 \le i, j \le k,\quad r_i \cdot r_j = r_i$.

$I$ = the $k \times k$ identity matrix

$U \in \mathbb R^{k \times k} = $ the matrix that is all ones $= \sum_{i=1}^k r_k$.

$D \in \mathbb R^{k \times k} = \text{Diag}(2^{k-1},2^{k-2},\dots,2^0)$

$e_i = $ the canonical ith basis vector in $\mathbb R^k$

From the above example, we see that, the state transition matrix for the ith player is $S_i = 2I - r_i.$

\begin{align} S_1 &= 2I - r_1\\ S_2 \cdot S_1 &= 4I - (2r_1 + r_2)\\ S_3 \cdot S_2 \cdot S_1 &= 8I - (4r_1 + 2r_2 + r_3)\\ & \vdots\\ S_k \cdots S_3 \cdot S_2 \cdot S_1 &= 2^kI - (2^{k-1}r_1 + 2^{k-2}r_2 + \cdots + r_k) \end{align}

We conclude that the state transition matrix for one round is

$ M = 2^kI - (2^{k-1}r_1 + 2^{k-2}r_2 + \cdots + r_k).$

Let the initial distribution of beans be $P = \begin{pmatrix}p_1\\ p_2\\ \vdots\\ p_k \end{pmatrix}$ and let $\tau = p_1 + p_2 + \cdots p_k$. We see that $r_i P = \tau e_i$ for all $i$.

So $MP = 2^k P - \tau(2^{k-1}e_1 + 2^{k-2}e_2 + \cdots + e_k)$

This means that, after one round, the i'th player has $2^k p_i - 2^{k-i}\tau$ beans.

A quick check show that , as the OP observed, $\tau$ is preserved.

After two rounds, the i'th player has $2^k(2^k p_i - 2^{k-i}\tau) - 2^{k-i}\tau =2^{2k} p_i - 2^{k-i}(2^k + 1)\tau$ beans.

After three rounds, the i'th player has $2^k(2^{2k} p_i - 2^{k-i}(2^k + 1)\tau) - 2^{k-i}\tau =2^{3k} p_i - 2^{k-i}(2^{2k} + 2^k + 1)\tau$ beans.

So after $n$ rounds, the i'th player has $2^{nk} p_i - 2^{k-i}(2^{(n-1)k} + \cdots + 2^{2k} + 2^k + 1)\tau = 2^{nk} p_i - 2^{k-i}(2^{nk} - 1)\tau$ beans.