## Problem 10

A and B play the following game with $\mathrm{N}$ counters. A divides the counters into 2 piles, each with at least 2 counters. Then B divides each pile into 2 piles, each with at least one counter. B then takes 2 piles according to a rule which both of them know, and A takes the remaining 2 piles. Both A and B make their choices in order to end up with as many counters as possible. There are 3 possibilities for the rule:

$R 1 \mathrm{~B}$ takes the biggest heap (or one of them if there is more than one) and the smallest heap (or one of them if there is more than one).

$R 2 \mathrm{~B}$ takes the two middling heaps (the two heaps that A would take under $R I$ ).

R3 B has the choice of taking either the biggest and smallest, or the two middling heaps. For each rule, how many counters will A get if both players play optimally?


## Solution

Answers: $[\mathrm{N} / 2],[(\mathrm{N}+1) / 2],[\mathrm{N} / 2]$.

Suppose A leaves piles $\mathrm{n}, \mathrm{m}$ with $\mathrm{n} \leq \mathrm{m}$.

Under $R 1$, B can certainly secure $\mathrm{m}$ by dividing the larger pile into 1 and $\mathrm{m}-1$. He cannot do better, because if $\mathrm{b}$ is the biggest of the 4 piles, then the smallest is at most m-b. Hence A's best strategy is to leave $[\mathrm{N} / 2],[(\mathrm{N}+1) / 2]$.

Under $R 2$, if A leaves $\mathrm{a}=2, \mathrm{~b}=\mathrm{N}-2$, then $\mathrm{B}$ cannot do better than [ $\mathrm{N} / 2]$, because if he divides the larger pile into $a, b$ with $a \leq b$, then he takes $a+1$. A cannot do better, because if he leaves $\mathrm{a}, \mathrm{b}$ with $3 \leq \mathrm{a} \leq \mathrm{b}$, then $\mathrm{B}$ can divide to leave $1, \mathrm{a}-1,[b / 2],[(b+1) / 2]$. Now if $\mathrm{a}-1 \geq[(b+1) / 2]$, then B takes $b \geq[(N+1) / 2]$. If $a-1<[(b+1) / 2]$, then $B$ takes $a-1+[b / 2]$. But $a-1 \geq 2$ and $[b / 2] \geq[(b+1) / 2]-$ 1 , so $\mathrm{a}-1+[\mathrm{b} / 2] \geq 1+[(\mathrm{b}+1) / 2]$, or $\mathrm{B}$ takes at least as many as A, so B takes at least $[(\mathrm{N}+1) / 2]$.

Under $R 3$, A's best strategy is to divide into $[\mathrm{N} / 2],[(\mathrm{N}+1) / 2]$. We have already shown that $\mathrm{B}$ can secure $[(\mathrm{N}+1) / 2]$ and no more by following $R 1$. He cannot do better under R2, for if he divides so that the biggest pile comes from [N/2], then the smallest does too and so he gets $[(\mathrm{N}+1) / 2]$. If he divides so that the biggest and smallest piles come from $[(\mathrm{N}+1) / 2]$, then he gets only [N/2]. But one of these must apply, because if he divided so that the smaller from $[\mathrm{N} / 2]$ was smaller than the smaller from $[(\mathrm{N}+1) / 2]$, and the bigger from $[\mathrm{N} / 2]$ was smaller than the bigger from $[(\mathrm{N}+1) / 2]$, then $[\mathrm{N} / 2]$ would be at least 2 less than $[(\mathrm{N}+1) / 2]$ (which it is not).

