Attrition by subtraction

The Game of Attrition works by players successively subtracting their own remaining number of points from their opponents points until one player is left with a nonpositive point total. Assume player A has $N$ points to begin the game and always goes first against his opponent B.

What is the largest point total that B can start with such that A will still win?

Let's say that B has initial points of $P > N,$ since obviously if $P \leq N,$ then A will win in the first move. After one round of both A and B's moves, A will have $2N-P$ points remaining and B will have $P-N,$ both of which are binomials in terms of $N$ and $P.$

Let $A_n$ and $B_n$ be the point total for A and B, respectively after $n$ full turns. One full turn of gameplay gives the following recurrence:

\begin{align*} A_{n+1} &= 2 A_n - B_n \\ B_{n+1} &= B_n - A_n \\ A_0 = N, \,\,&\,\, B_0 = P\end{align*}

If we assume, as after the first turn, that both $A_n$ and $B_n$ are binomials in terms of $N$ and $P$, say $A_n = a_n N + b_n P$ and $B_n = c_n N + d_n P,$ then the above recurrence becomes \begin{align*} a_{n+1} &= 2 a_n - c_n \\ b_{n+1} &= 2 b_n - d_n \\ c_{n+1} &= c_n - a_n \\ d_{n+1} &= d_n - b_n \\ a_0 = d_0 = 1, \,\,&\,\, b_0 = c_0 = 0 \end{align*} We note that player $A$ will win after $n$ steps if $B_n \leq 0,$ or equivalently, if $$P \leq -\frac{c_n}{d_n} N.$$ The largest possible point total that B can start with such that A will still win is thus $$\sup \left\{ -\frac{c_n}{d_n}N : n \in \mathbb{N} \right\}.$$

Letting $x_n = (a_n, b_n, c_n, d_n)^T,$ and $$M =\left(\begin{array}{cccc} 2 & 0 & -1 & 0 \\ 0 & 2 & 0 & -1 \\ -1 & 0 & 1 & 0 \\ 0 & -1 & 0 & 1 \end{array}\right),$$ we can express the reccurence more compactly in matrix notation as: $$x_n = Mx_{n-1} = \cdots = M^n x_0,$$ where $x_0 = (1, 0, 0, 1)^T.$ The matrix $M$ has eigenvalues $\lambda_\pm = \frac{3 \pm \sqrt{5}}{2},$ each of order $2,$ associated with eigenvectors $$u_\pm = \sqrt{\frac{2}{5\mp \sqrt{5}}}\left( \begin{array}{c} 1 \\ 0 \\ \frac{1 \mp \sqrt{5}}{2} \\ 0\end{array} \right) \,\,\, \text{and} \,\,\, v_\pm = \sqrt{\frac{2}{5\mp \sqrt{5}}} \left( \begin{array}{c} 0 \\ 1 \\ 0 \\ \frac{1 \mp \sqrt{5}}{2}\end{array} \right).$$ So let's define $$L = \left(\begin{array}{cccc} 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ -\frac{\sqrt{5}-1}{2} & 0 & \frac{\sqrt{5} + 1}{2} & 0 \\ 0 & -\frac{\sqrt{5}-1}{2} & 0 & \frac{\sqrt{5} + 1}{2}\end{array}\right),$$ $$D = \left(\begin{array}{cccc} \frac{5-\sqrt{5}}{2} & 0 & 0 & 0 \\ 0 & \frac{5 - \sqrt{5}}{2} & 0 & 0 \\ 0 & 0 & \frac{5 + \sqrt{5}}{2} & 0 \\ 0 & 0 & 0 & \frac{5 + \sqrt{5}}{2}\end{array}\right) = L^TL$$ and $$\Lambda = \left(\begin{array}{cccc} \frac{3+\sqrt{5}}{2} & 0 & 0 & 0 \\ 0 & \frac{3+\sqrt{5}}{2} & 0 & 0 \\ 0 & 0 & \frac{3-\sqrt{5}}{2} & 0 \\ 0 & 0 & 0 & \frac{3-\sqrt{5}}{2}\end{array}\right).$$ Then the eigendecomposition of $M$ can be given by $M = Q \Lambda Q^T,$ where $Q = LD^{-1/2}.$ In particular, for any integer $n \geq 1,$ $$M^n = Q\Lambda^n Q^T = (LD^{-1/2})\Lambda^n (LD^{-1/2})^T = L D^{-1} \Lambda^n L^T.$$

For any integer $n \geq 1,$ $$D^{-1} \Lambda^n L^T x_0 = \left( \begin{array}{c} \frac{2}{5-\sqrt{5}} \left( \frac{3+\sqrt{5}}{2} \right)^n \\ -\frac{\sqrt{5}}{5} \left( \frac{3+\sqrt{5}}{2} \right)^n \\ \frac{2}{5+\sqrt{5}} \left( \frac{3-\sqrt{5}}{2} \right)^n \\ \frac{\sqrt{5}}{5}\left( \frac{3-\sqrt{5}}{2} \right)^n\end{array} \right).$$ So the recurrence relationship can be written as $x_n = M^n x_0 = L D^{-1} \Lambda^n L^T x_0,$ which is given by \begin{align*}x_n = M^n x_0 &= \left( \begin{array}{cccc} 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ -\frac{\sqrt{5}-1}{2} & 0 & \frac{\sqrt{5} + 1}{2} & 0 \\ 0 & -\frac{\sqrt{5}-1}{2} & 0 & \frac{\sqrt{5} + 1}{2}\end{array} \right) \left( \begin{array}{c} \frac{2}{5-\sqrt{5}} \left( \frac{3+\sqrt{5}}{2} \right)^n \\ -\frac{\sqrt{5}}{5} \left( \frac{3+\sqrt{5}}{2} \right)^n \\ \frac{2}{5+\sqrt{5}} \left( \frac{3-\sqrt{5}}{2} \right)^n \\ \frac{\sqrt{5}}{5}\left( \frac{3-\sqrt{5}}{2} \right)^n\end{array} \right)\\ &= \left( \begin{array}{c} \frac{2}{5-\sqrt{5}}\left(\frac{3+\sqrt{5}}{2} \right)^n + \frac{2}{5+\sqrt{5}}\left(\frac{3-\sqrt{5}}{2} \right)^n \\ -\frac{\sqrt{5}}{5} \left(\frac{3+\sqrt{5}}{2} \right)^n + \frac{\sqrt{5}}{5} \left(\frac{3-\sqrt{5}}{2} \right)^n \\ -\frac{\sqrt{5}}{5} \left(\frac{3+\sqrt{5}}{2} \right)^n + \frac{\sqrt{5}}{5} \left(\frac{3-\sqrt{5}}{2} \right)^n \\ \frac{\sqrt{5}(\sqrt{5}-1)}{10} \left(\frac{3 + \sqrt{5}}{2}\right)^n + \frac{\sqrt{5}(\sqrt{5}+1)}{10} \left(\frac{3 - \sqrt{5}}{2}\right)^n \end{array} \right).\end{align*} Therefore, we have $$-\frac{c_n}{d_n} N = \frac{ \frac{\sqrt{5}}{5} \left(\frac{3+\sqrt{5}}{2} \right)^n - \frac{\sqrt{5}}{5} \left(\frac{3-\sqrt{5}}{2} \right)^n }{ \frac{\sqrt{5}(\sqrt{5} - 1)}{10} \left(\frac{3+\sqrt{5}}{2} \right)^n + \frac{\sqrt{5}(\sqrt{5} + 1)}{10} \left(\frac{3-\sqrt{5}}{2} \right)^n } N,$$ which is a monotonically increasing sequence with $$\lim_{n\to \infty} -\frac{c_n}{d_n} N = \sup \left\{ -\frac{c_n}{d_n} N : n \in \mathbb{N}\right\} = \frac{\sqrt{5}+1}{2}N.$$ That is, if $P \leq \frac{\sqrt{5}+1}{2} N,$ then A will still win, or more specifically, the function $$P(N) = \left\lfloor \frac{\sqrt{5}+1}{2} N \right\rfloor$$ gives the maximal value that B can start with but lose to $A$, who starts with N and goes first.