Directed Grabbing Games or How to Politely Grab the Maximum Number of Olives in a Reception

Let $\sigma$ and ${\sigma }^{\prime }$ be optimal plays for $(D,w)$ and $(D,w^{\prime })$ respectively. We have $\mathrm{val}(D,w,\sigma )=\mathrm{opt}(D,w)$ and $\mathrm{val}(D,w^{\prime },{\sigma }^{\prime })=\mathrm{opt}(D,w^{\prime })$.

Similarly we get $\mathrm{opt}(D,w^{\prime })\ge opt(D,w)-d$. $◀$

A maximum-weight vertex in $(D,w)$ is a vertex $x$ such that $w(x)\ge w(v)$ for all $v\in V(D)$.

We prove the result by induction on the number of vertices of $D$, the result holding trivially for $|V(D)|=1$.

Assume now that $|V(D)|\ge 2$, and that there is a vertex $x$ with out-degree $0$ with maximum weight. Let $\sigma =(v_1,v_2,\mathrm{\dots },v_n)$ be an optimal play for $(D,w)$. If $x=v_1$, then we have the result. Henceforth, we may assume that $x\ne v_1$. Now, the induction hypothesis applied to $(D-v_1,w)$ (in which $x$ is a sink and a maximum-weight vertex) implies that there is an optimal play for $(D-v_1,w)$ starting with $x$. Thus, we may assume that $x=v_2$. Let $D^{\ast }=D-\{v_1,v_2\}=D-\{v_1,x\}$. We have $\mathrm{opt}(D,w)=\mathrm{val}(D,w,\sigma )=w(v_1)-w(x)+\mathrm{opt}(D^{\ast },w)$.

Let ${\max }_x$ be the maximal value of a play starting with $x$ and optimal afterwards. ${\max }_x=w(x)-\mathrm{opt}(D-x,w)$. Let $w^{\prime }$ be the weight function defined on $D-x$ by $w^{\prime }(u)=w(x)$ if $u=v_1$ and $w^{\prime }(u)=w(u)$ otherwise. Observe that in $(D-x,w^{\prime })$, $v_1$ is a sink and a maximum-weight vertex. By the induction hypothesis, there is an optimal play starting with $v_1$. So $\mathrm{opt}(D-x,w^{\prime })=w^{\prime }(v_1)-\mathrm{opt}(D^{\ast },w^{\prime })=w(x)-\mathrm{opt}(D^{\ast },w)$. Thus, by Lemma 1, $\mathrm{opt}(D-x,w)\le \mathrm{opt}(D-x,w^{\prime })+w(x)-w(v_1)=2w(x)-w(v_1)-\mathrm{opt}(D^{\ast },w)$. Hence ${\max }_x\ge w(v_1)-w(x)+\mathrm{opt}(D^{\ast },w)=\mathrm{opt}(D,w)$. Therefore, there is an optimal play starting with $x$. $◀$

Assume $|V(D)|$ is even.

Bob can play the following strategy. Bob never removes vertex $x^{+}$. This is possible because $|V(D)|$ is even and $x^{+}$ has to be removed before $x$. If Alice removes a vertex in $D-\{x,x^{+}\}$, then Bob plays according to an optimal strategy on $(D-\{x,x^{+}\},w)$. If Alice removes $x^{+}$, then Bob removes $x$. Doing so Bob collects at least ${\mathrm{gain}}^B(D-\{x,x^{+}\},w)+w(x)$ so

Alice can play the following strategy. If Bob removes $x^{+}$, then Alice removes $x$. Otherwise she removes if possible a vertex of $D-\{x,x^{+}\}$; but as $|V(D)|$ is even, at the end Alice is forced to remove $x^{+}$. Doing so, Alice collects either ${\mathrm{gain}}^A(D-\{x,x^{+}\},w)+w(x)$ if Bob removes $x^{+}$, or ${\mathrm{gain}}^A(D-\{x,x^{+}\},w)+w(x^{+})$ if Alice removes $x^{+}$ at the end. Since $w(x^{+})\le w(x)$, we get

Finally, as ${\mathrm{gain}}^A(D,w)+{\mathrm{gain}}^B(D,w)={\mathrm{gain}}^A(D-\{x,x^{+}\},w)+{\mathrm{gain}}^B(D-\{x,x^{+}\},w)+w(x)+w(x^{+})$, Inequalities (1) and (2) imply ${\mathrm{gain}}^A(D,w)={\mathrm{gain}}^A(D-\{x,x^{+}\},w)+w(x^{+})$ and ${\mathrm{gain}}^B(D,w)={\mathrm{gain}}^B(D-\{x,x^{+}\},w)+w(x)$ and so $\mathrm{val}(D,w)=\mathrm{val}(D-\{x,x^{+}\},w)+w(x^{+})-w(x)$.

When $|V(D)|$ is odd, the proof is similar with the role of Alice and Bob interchanged. $◀$

We first prove that $\mathrm{val}(D,w)\le \mathrm{val}(D^{\ast },w^{\ast })$.

To do so we construct simultaneously move by move two plays, one in $(D,w)$ and one in $(D^{\ast },w^{\ast })$. In $(D,w)$, Alice plays an optimal strategy resulting in a play denoted by ${\sigma }_{opt}^A$ and in $(D^{\ast },w^{\ast })$ Bob plays an optimal strategy resulting in a play denoted by ${\sigma }_{opt}^{\ast B}$. In $(D^{\ast },w^{\ast })$, we construct an $A$-play ${\sigma }^{\ast A}$ (not necessarily optimal) for Alice which follows (mimics) ${\sigma }_{opt}^A$ and in $(D,w)$ we construct a $B$-play ${\sigma }^B$ (not necessarily optimal) for Bob which follows ${\sigma }_{opt}^{\ast B}$. In particular, if Alice removes, according to ${\sigma }_{opt}^A$, a vertex $v$ not in $\{v_p,v_{p-1},\mathrm{\dots },v_{i+1},v_i,v_{i-1}\}$, we impose that Alice removes the same vertex $v$ in the simultaneous move in $(D^{\ast },w^{\ast })$. Similarly, if Bob removes, according to ${\sigma }_{opt}^{\ast B}$, a vertex $v$ not in $\{v_p,v_{p-1},\mathrm{\dots },v_{i+2},,v_i^{\ast }\}$, we impose that Bob removes the same vertex $v$ in the simultaneous move in $(D,w)$.

We consider the first move $m$ when either Bob removes vertex $v_i^{\ast }$ in $(D^{\ast },w^{\ast })$ with $B$-play ${\sigma }_{opt}^{\ast B}$ (Case 1) or Alice removes vertex $v_{i-1}$ in $(D,w)$ with $A$-play ${\sigma }_{opt}^A$ (Case 2). Note that in the moves strictly before $m$, Alice has been imposed to remove the same vertices in $(D^{\ast },w^{\ast })$ and $(D,w)$ because ${\sigma }^{\ast A}$ follows ${\sigma }_{opt}^A$, and Bob has been imposed to remove the same vertices in $(D,w)$ and $(D^{\ast },w^{\ast })$ because ${\sigma }^B$ follows ${\sigma }_{opt}^{\ast B}$.

• $\mathrm{■}$

  Case 1: At move $m$ (even), Bob removes vertex $v_i^{\ast }$ with $B$-play ${\sigma }_{opt}^{\ast B}$ in $(D^{\ast },w^{\ast })$ and $v_{i-1}$ has not been removed in $(D,w)$ by Alice with strategy ${\sigma }_{opt}^A$. In that case, the vertices $v_1,\mathrm{\dots }{v}_{i-2}$ have been all removed in $(D,w)$ and $(D^{\ast },w^{\ast })$ and we impose Bob to remove vertex $v_{i-1}$ within ${\sigma }^B$ at move $m$.

  Let $\mu$ be the first move after $m$ when Alice removes a vertex in $P$ with $A$-play ${\sigma }_{opt}^A$ in $(D,w)$. In the odd moves strictly before $\mu$ (if any), Alice removes a vertex $v$ not in $P$ with $A$-play ${\sigma }_{opt}^A$ in $(D,w)$, and we impose that Alice removes the same vertex $v$ in the simultaneous move in $(D^{\ast },w^{\ast })$. In the even moves strictly before $\mu$, if Bob removes a vertex $v$ in $D^{\ast }$ not in $P$ with $B$-play ${\sigma }_{opt}^{\ast B}$, we impose that Bob removes the same vertex $v$ in the simultaneous move in $(D,w)$. If Bob removes a vertex $v_k$ ($i+2\le k\le p)$ in $(D^{\ast },w^{\ast })$ with $B$-play ${\sigma }_{opt}^{\ast B}$, we impose that, in the simultaneous move in $(D,w)$, Bob removes the vertex $v_{k-2}$ which is the first available. We note that move $\mu$ exists because, as with the above conditions, Bob will not remove $v_{p-1}$ before Alice removes a vertex of $P$. We also note that $\mu$ is odd and $m+1\le \mu \le n-2$.

  Let $v_j$ ($i\le j\le p-1$) be the vertex removed by Alice at move $\mu$. Then we impose that Bob removes with $B$-play ${\sigma }^B$ in move $\mu +1$ vertex $v_{j+1}$. Then, for the end of the plays, we impose that Alice removes with $A$-play ${\sigma }^{\ast A}$ in $(D^{\ast },w^{\ast })$ at move $\mu +2h$ ($h\ge 0$) the same vertex as the one removed by Alice in $(D,w)$ at move $\mu +2+2h$ with $A$-play ${\sigma }_{opt}^A$. We impose that Bob removes in $(D,w)$ at move $\mu +3+2h$ ($h\ge 0$) the same vertex as the one removed by Bob with $B$-play ${\sigma }_{opt}^{\ast B}$ in $(D^{\ast },w^{\ast })$ at move $\mu +1+2h$.

  In summary in this Case 1, Alice has removed in $(D,w)$ (according to $\sigma ={\sigma }_{opt}^A\oplus {\sigma }^B$) the same vertices as in $(D^{\ast },w^{\ast })$ (according to ${\sigma }^{\ast }={\sigma }^{\ast A}\oplus {\sigma }_{opt}^{\ast B}$) plus $v_j$. As $w(v_j)\le w(v_i)$ for $j\ge i$, we have:

  ${\mathrm{col}}^A(D,w,\sigma )={\mathrm{col}}^A(D^{\ast },w^{\ast },{\sigma }^{\ast })+w(v_j)\le {\mathrm{col}}^A(D^{\ast },w^{\ast },{\sigma }^{\ast })+w(v_i).$

• $\mathrm{■}$

  Case 2: At move $m$ (odd), Alice removes vertex $v_{i-1}$ with $A$-play ${\sigma }_{opt}^A$ in $(D,w)$ and $v_i^{\ast }$ has not been removed by Bob with $B$-play ${\sigma }_{opt}^{\ast B}$ in $(D^{\ast },w^{\ast })$. Then we impose that Bob removes vertex $v_i$ within ${\sigma }^B$ at move $m+1$.

  We also impose that in all the moves after $m+1$, if Alice removes a vertex $v\ne v_{i+1}$ with $A$-play ${\sigma }_{opt}^A$ at a move $m+2+2h$, then Alice removes the same vertex $v$ in move $m+2h$ in $(D^{\ast },w^{\ast })$ with $A$-play ${\sigma }^{\ast A}$. We also impose that, if Bob removes vertex $v\ne v_i^{\ast }$ at move $m+1+2h$ with $B$-play ${\sigma }_{opt}^{\ast B}$ in $(D^{\ast },w^{\ast })$, then Bob removes the same vertex in $(D,w)$ at move $m+3+h$ with $B$-play ${\sigma }^B$.

  We now distinguish two sub-cases.

  • –

    Sub-case 2.1: Alice removes vertex $v_{i+1}$ with ${\sigma }_{opt}^A$ at some odd move $\mu >m$. Bob cannot have removed vertex $v_i^{\ast }$ in $(D^{\ast },w^{\ast })$ with ${\sigma }_{opt}^{\ast B}$ in a move before $\mu -3$ otherwise Bob would have removed $v_{i+1}$ in a move before $\mu -1$ and so $v_{i+1}$ cannot be removed by Alice at move $\mu$. Then we impose that Alice removes vertex $v_i^{\ast }$ at move $\mu -2$ in $(D^{\ast },w^{\ast })$ with ${\sigma }^{\ast A}$. Therefore Bob cannot remove $v_i^{\ast }$.

  • –

    Sub-case 2.2: Bob removes vertex $v_i^{\ast }$ with ${\sigma }_{opt}^{\ast B}$ at some even move $\nu >m$. Alice cannot have removed $v_{i+1}$ in $(D,w)$ at a move before $\nu +1$, otherwise Alice would have removed $v_i^{\ast }$ in $(D^{\ast },w^{\ast })$ before move $\nu -1$. Then we impose that Bob removes vertex $v_{i+1}$ at move $\nu +2$ in $(D,w)$ with ${\sigma }^B$ and so Alice will never remove $v_{i+1}$.

  In Sub-case 2.1, Alice has removed the same vertices in $D-\{v_{i-1},v_i,v_{i+1}\}$ as in $D^{\ast }$. Furthermore Alice has removed $v_{i-1}$ and $v_{i+1}$ in $D$ while Alice has removed $v_i^{\ast }$ in $D^{\ast }$ with weight $w^{\ast }(v_i^{\ast })=w(v_{i-1})+w(v_{i+1})-w(v_i)$. Thus:

  ${\mathrm{col}}^A(D,w,\sigma )\le {\mathrm{col}}^A(D^{\ast },w^{\ast },{\sigma }^{\ast })+w(v_i).$

  In Sub-case 2.2, Alice has removed the same vertices in $D$ as in $D^{\ast }$ plus $v_{i-1}$. Thus:

  ${\mathrm{col}}^A(D,w,\sigma )\le {\mathrm{col}}^A(D^{\ast },w^{\ast },{\sigma }^{\ast })+w(v_{i-1})\le {\mathrm{col}}^A(D^{\ast },w^{\ast },{\sigma }^{\ast })+w(v_i).$

Recall that $\mathrm{val}(D,w)={\mathrm{gain}}^A(D,w)-{\mathrm{gain}}^B(D,w)$ and ${\sum }_{v\in D}w(v)={\mathrm{gain}}^A(D,w)+{\mathrm{gain}}^B(D,w)$. Thus $\mathrm{val}(D,w)=2{\mathrm{gain}}^A(D,w)-{\sum }_{v\in D}w(v)$. Similarly, $\mathrm{val}(D^{\ast },w^{\ast })=2{\mathrm{gain}}^A(D^{\ast },w^{\ast })-{\sum }_{v\in D^{\ast }}{w}^{\ast }(v)$. Moreover, by construction, ${\mathrm{\Sigma }}_{v\in D}w(v)={\mathrm{\Sigma }}_{v\in D^{\ast }}{w}^{\ast }(v)-2w(v_i)$.

${\sigma }_{opt}^A$ is a play obtained by playing an optimal strategy and ${\sigma }^B$ is not necessarily optimal, thus ${\mathrm{gain}}^A(D,w)\le {\mathrm{col}}^A(D,w,\sigma )$. As in both above subcases ${\mathrm{col}}^A(D,w,\sigma )\le {\mathrm{col}}^A(D^{\ast },w^{\ast },{\sigma }^{\ast })+w(v_i)$, we get:

Now ${\sigma }_{opt}^{\ast B}$ is a $B$-play obtained by playing an optimal strategy and ${\sigma }^{\ast A}$ is not necessarily optimal. Thus ${\mathrm{col}}^A(D^{\ast },w^{\ast },{\sigma }^{\ast })\le {\mathrm{gain}}^A(D^{\ast },w^{\ast })$ and so

One can prove $\mathrm{val}(D^{\ast },w^{\ast })\le \mathrm{val}(D,w)$ in a similar way. More precisely, Alice plays in $(D^{\ast },w^{\ast })$ an optimal strategy resulting in a $A$-play ${\sigma }_{opt}^{A\ast }$ and Bob plays in $(D,w)$ an optimal strategy resulting in a ${\sigma }_{opt}^B$. We construct in $(D,w)$ an $A$-play ${\sigma }^A$ for Alice that follows ${\sigma }_{opt}^{\ast }$, and in $(D^{\ast },w^{\ast })$ a $B$-play ${\sigma }^{\ast B}$ for Bob that follows ${\sigma }_{opt}$. The proof is the same as above by interchanging the roles of Alice and Bob. $◀$

The algorithm proceeds at follows. It first reduces each component of $D$ using the first and second reduction. Note that this can be done in linear time in $n$ since the reduction applies (if any) around the smallest index $i$ such that $w(v_i)\ge w(v_{i-1})$.

After such a reduction, we obtain a union of disjoint directed paths such that the weight function is strictly increasing on each directed path. In particular, at each turn the maximum-weight vertex will be a sink and thus removable. Therefore, by an easy induction with Lemma 2, there is an optimal play in which each player removes the maximum-weight vertex at each step. Hence, it suffices to sort the vertices in increasing order of their weight to get an optimal play. This corresponds to merging the $q$ sorted lists into a single sorted list, which can be done in $O(n\log q)$ time using heaps. $◀$

1. (i)

   When $q$ is even, Bob can apply the following strategy.

   If Alice removes $(i,2j-1)$ for some $i\in [p]$ and $j\in [q/2]$, then Bob removes $(i,2j)$.

   Observe that Bob can apply this strategy all play long. Indeed when it is Alice’s turn to play, only vertices in odd-columns are removable. Doing so Bob remove all vertices of ${ℂ}_{\mathrm{even}}$.

2. (ii)

   Symmetrically, when $p$ is even, Bob can apply the following strategy and remove all vertices of ${ℝ}_{\mathrm{even}}$.

   If Alice removes $(2i-1,j)$ for some $i\in [p/2]$ and $j\in [q]$, then Bob removes $(2i,j)$.

$◀$

When $p$ and $q$ have different parities, Bob can apply similar strategies, either for odd columns if $p$ is even after some bootstrap in the first column, or for odd rows if $q$ is even after some bootstrap in the first row. These two strategies are symmetric to each other.

1. (i)

   Assume $p$ is even and $q$ is odd. Bob can apply the following strategy.

   If Alice removes a vertex $(2i-1,1)$ for some $i\in [p/2]$, then Bob removes $(2i,1)$.
   If Alice removes a vertex $(i,2j)$ for some $j\in [\lfloor q-1/2\rfloor ]$, then Bob removes the vertex $(i,2j+1)$.

   When it is Alice’s turn to play, two cases may occur. If the first column has not been fully removed, then the removable vertices are one odd-row vertex in the first column and some vertices in even columns. If the first column has been removed and perhaps some pairs of columns (in an even number of moves as $p$ is even), then only vertices in even columns are removable. In both cases, Alice can never remove a vertex in ${ℂ}_{\mathrm{odd}}^0$.

2. (ii)

   Assume $p$ is odd and $q$ is even. The proof of (ii) is symmetric to (i). An ${ℝ}_{\mathrm{odd}}^0$-strategy for Bob is the following.

   If Alice removes a vertex $(1,2j-1)$ for some $j\in [q/2]$, then Bob removes $(1,2j)$.
   If Alice removes a vertex $(2i,j)$ for some $i\in [\lfloor p-1/2\rfloor ]$, then Bob removes the vertex $(2i+1,j)$.

$◀$

We now give some strategies for Alice when $pq$ is odd.

1. (i)

   Assume $p$ and $q$ are both odd. Alice can apply the following strategy.

   If Bob removes a vertex $(2i,1)$ for some $i\in [(p-1)/2]$, then Alice removes $(2i+1,1)$.
   If Bob removes a vertex $(i,2j)$ for some $j\in [(q-1)/2]$, then Alice removes $(i,2j+1)$.

   When it is Bob’s turn to play, two cases may occur. If the first column has not been fully removed, then the removable vertices are one even-row vertex in the first column and some vertices in even columns (indeed as $q$ is odd Alice could have applied the second rule). If the first column has been removed and perhaps some pairs of others consecutive even-odd columns (in an odd number of moves as $p$ is odd), then only vertices in even columns are removable. In both cases, Bob can never remove a vertex in ${ℂ}_{\mathrm{odd}}^1$.

2. (ii)

   The proof is symmetric to (i). An ${ℝ}_{\mathrm{odd}}^1$-strategy for Alice is the following.

   If Bob removes a vertex $(1,2j)$ for some $j\in [(q-1)/2]$, then Alice removes $(1,2j+1)$.
   If Bob removes a vertex $(2i,j)$ for some $i\in [(p-1)/2]$, then Alice removes $(2i+1,j)$.

$◀$

We now describe more elaborate strategies which will enable Alice or Bob to remove vertices not removed by the simple strategies above. Let us specify some definitions and notations.

A configuration of the play on the $p\times q$ grid at time $t$ is completely determined by the numbers $r_i^t$ of vertices that have not been removed from rows $R_i$. Said otherwise, vertex $(i,j)$ has been removed for $1\le j\le q-r_i^t$ and vertex $(i,j)$ has not been removed for $q+1-r_i^t\le j\le q$. Clearly, at any time $t$, we have $0\le r_i^t\le r_{i+1}^t\le q$. At the beginning of the game (time $0$), we have $r_i^0=q$ for all $i\in [p]$. At time $t$, we have ${\sum }_{i=1}^p{r}_i^t=pq-t$. This sum is even when either $t$ is odd and $pq$ is odd, or $t$ is even and $pq$ is even.

We note that a vertex is removable at move $t+1$ if it is of the form $(i,q+1-r_i^t)$ with $r_i^t>r_{i-1}^t$. Furthermore if $r_i^t>r_{i-1}^t+1$, then after the removal of $(i,q+1-r_i^t)$ at move $t+1$, we have $r_i^{t+1}=r_i^t-1>r_{i-1}^t$, so the vertex to the right $(i,q+2-r_i^t)$ becomes removable.

A configuration on the $p\times q$ grid at time $t$ odd is $A$-good if there exists a non-negative $i_0^t$, shortly denoted by $i_0$, such that

1. 1.

   $r_{2i-1}^t=r_{2i}^t$ for $i\le i_0$,

2. 2.

   $r_{2i_0+1}^t$ is even, and

3. 3.

   $r_i^t$ is odd for $2i_0+2\le i\le p$.

Observe that if the configuration at time $t$ odd is $A$-good, no vertex of ${ℝ}_{\mathrm{even}}\cap {ℂ}_{\mathrm{even}}$ is removable by Bob at move $t+1$. Indeed, recall that a removable vertex is of the form $(i,q+1-r_i^t)$ with $r_i^t>r_{i-1}^t$. For $i\le 2i_0+1$, there are only removable vertices in odd rows, and so not in ${ℝ}_{\mathrm{even}}\cap {ℂ}_{\mathrm{even}}$. For $i>2i_0+1$, $r_i^t$ is odd, so a removable vertex in row $i$ is in an odd column and so not in ${ℝ}_{\mathrm{even}}\cap {ℂ}_{\mathrm{even}}$.

Hence, it suffices for Alice to leave an $A$-good configuration after each of her moves to collect all vertices of ${ℝ}_{\mathrm{even}}\cap {ℂ}_{\mathrm{even}}$. We shall now prove by induction on $t$, that Alice has a strategy to do so. In her first move, Alice necessarily removes vertex $(1,1)$. So $r_1^1=q-1$ (which is even) and $r_i^1=q$ (which is odd) for all $2\le i\le p$. Thus, the configuration at time $1$ is $A$-good with $i_0=0$. This proves the base case of the induction. The inductive case is the following claim.

• $\mathrm{■}$

  Suppose Bob removes vertex $(i_1,q+1-r_{i_1}^t)$ in a row (at move $t+1$).

  Hence $i_1$ is necessarily odd. Then Alice removes the vertex below $(i_1+1,q+1-r_{i_1+1}^t)$ which is now removable as $r_{i_1+1}^{t+1}=r_{i_1+1}^t=r_{i_1}^t=r_{i_1}^{t+1}+1$. Consequently, $r_{i_1+1}^{t+2}=r_{i_1+1}^t-1=r_{i_1}^t-1=r_{i_1}^{t+2}$, and $r_i^{t+2}=r_i^t$ for all $i\notin \{i_1,i_1+1\}$. Hence, since the configuration at time $t$ was $A$-good, so the configuration at time $t+2$ is also $A$-good with $i_0^{t+2}=i_0$.

• $\mathrm{■}$

  Suppose Bob removes vertex $(2i_0+1,q+1-r_{2i_0+1}^t)$. Necessarily, $r_{2i_0+1}^t>r_{2i_0}^t$.

  If $r_{2i_0+1}^t>r_{2i_0}^t+1$, Alice removes the vertex on the right $(2i_0+1,q+2-r_{2i_0+1}^t)$. Consequently, $r_{2i_0+1}^{t+2}=r_{2i_0+1}^t-2$ (which is even) and $r_i^{t+2}=r_i^t$ for all $i\notin \{2i_0+1\}$. Hence, since the configuration at time $t$ was $A$-good, so is the configuration at time $t+2$ with $i_0^{t+2}=i_0$.

  If $r_{2i_0+1}^t=r_{2i_0}^t+1$, we note that $r_{2i_0-1}^t=r_{2i_0}^t=r_{2i_0+1}^t-1$ is odd. Let $i_3$ be the smallest value such that $r_{2i_3+1}^t=r_{2i_3+2}^t=r_{2i_0+1}^t-1$. Then $(2i_3+1,q+1-r_{2i_3+1})$ is removable and Alice removes it. Then $r_{2i_3+1}^{t+2}=r_{2i_3+1}^t-1$ is even. Furthermore, for all , $r_i^{t+2}$ is odd. So the configuration at time $t+2$ is $A$-good with $i_0^{t+2}=i_3$.

• $\mathrm{■}$

  Suppose Bob removes vertex $(2i_0+2,q+1-r_{2i_0+2}^t)$. That implies that $r_{2i_0+2}^t>r_{2i_0+1}^t$.

  If $r_{2i_0+2}^t>r_{2i_0+1}^t+1$, then Alice removes the vertex on the right $(2i_0+2,q+2-r_{2i_0+2}^t)$. This results in an $A$-good configuration with $i_0^{t+2}=i_0$ because $r_{2i_0+2}^{t+2}=r_{2i_0+2}^t-2$ is odd, and $r_i^{t+2}=r_i^t$ for all $i\ne 2i_0+2$.

  If $r_{2i_0+2}^t=r_{2i_0+1}^t+1$, then Alice removes the vertex below $(2i_0+3,q+1-r_{2i_0+3}^t)$. This results in an $A$-good configuration with $i_0^{t+2}=i_0+1$ because $r_{2i_0+3}^{t+2}=r_{2i_0+3}^t-1$ is even, $r_{2i_0+1}^{t+2}=r_{2i_0+2}^{t+2}=r_{2i_0+1}^t$, and $r_i^{t+2}=r_i^t$ for all $i\notin \{2i_0+2,2i_0+3\}$.

• $\mathrm{■}$

  Suppose Bob removes a vertex $(i,q+1-r_i^t)$ with $i>2i_0+2$. Note that $r_i^t>r_{i-1}^t+1$ (as both values are odd) and so Alice removes vertex $(i,q+2-r_i^t)$. This results in an $A$-good configuration with $i_0^{t+2}=i_0$ because $r_i^{t+2}=r_i^t-2$ is odd, and $r_i^{t+2}=r_i^t$ for all $i\ne 2i_0+2$.