Solution:

(a)
We call a general pair of starting values $(a, b)$ good if Paul has a winning strategy for it. For completeness, we also allow $a=0$ or $b=0$ and call $(0,0)$ good. Analogously, we call all pairs that are not good bad and note that for these starting values, Henning obviously has a winning strategy. We use the following general principle:
If $(a, b)$ is good, then $(a+n, b)$, $(a, b+n)$, $(a+n, b+n)$ are bad for every $n \in \mathbb{N}$, since Henning can simply reach $(a, b)$ in his first move, and then Paul must start a new game with starting values that are now good for Henning. Thus, for each $a$ there is at most one $b$ such that $(a, b)$ is good.
Furthermore: If Henning can only reach bad positions in his first move from $(a, b)$, then $(a, b)$ is good, because Paul then has a winning strategy regardless of Henning's move, by the above remark.
Now suppose that $A$ has only finitely many elements. Then there are also only finitely many good starting values (since for each good position, by the above principle and because $(a, b)$ good $\Longleftrightarrow (b, a)$ good, there is exactly one element from $A$, namely the smaller of the two starting values). In particular, there is a number $C$ strictly greater than all $a, b$ with $(a, b)$ good. However, for $(C, 2C)$, the pairs $(C-n, 2C)$, $(C-n, 2C-n)$ for each $n \in \{1,2, \ldots, C\}$ and $(C, 2C-m)$ for each $m \in \{1,2, \ldots, 2C\}$ are bad by the construction of $C$, so $(C, 2C)$ is good. Contradiction!

(b)
We first show that every natural number occurs either in $A$ or in $B = \{b_{k} \mid (a_{k}, b_{k}) \text{ good}\}$. What we found in part (a) implies that a natural number cannot occur in both sets. Suppose there is an $n \in \mathbb{N}$ such that $n$ occurs in neither $A$ nor $B$, and choose $n$ minimal. In other words, for all $m \in \mathbb{N}$, the pair $(m, n)$ is bad. But this also means that for each $m$, one of the pairs $(m, n-1), (m, n-2), \ldots, (m, 0), (m-1, n-1), (m-2, n-2), \ldots, (m-\min\{m, n\}, n-\min\{m, n\})$ is good. For example, consider $m = n+1, 2n+1, 3n+1, \ldots, (n+1)n+1$; all these tuples are pairwise distinct.
Thus, by our assumption, we obtain $n+1$ different good pairs, all of the form $(x, y)$ with $y \in \{0,1, \ldots, n-1\}$. However, by the pigeonhole principle, two $y$ must take the same value, which contradicts our intermediate result from (a). Thus, $A \sqcup B = \mathbb{N}$.

The next step is to show that $a_{k} - b_{k} = k$ holds for all $k \in \mathbb{N}$ and that $b_{k} = \min \left(\mathbb{N} \setminus \{a_{1}, \ldots, a_{k-1}, b_{1}, \ldots, b_{k-1}\}\right)$. This is easily found by trial and can be proved by induction.
- Base case: Obviously, $a_{0} = 0, b_{0} = 0$ and $a_{1} = 2, b_{1} = 1$ are the first good pairs and satisfy the statement.
- Assume that the numbers $a_{1}, \ldots, a_{n}$ and $b_{1}, \ldots, b_{n}$ satisfy the statement. Now set $b_{n+1} = \min \left(\mathbb{N} \setminus \{a_{1}, \ldots, a_{n}, b_{1}, \ldots, b_{n}\}\right)$. Since by the induction hypothesis $b_{k} < b_{n+1}$ for all $k \leq n$, it follows that $b_{n+1} + n + 1 > b_{k} + k = a_{k}$ for all $k \leq n$. In particular, we can set $a_{n+1} = b_{n+1} + n + 1$, since this is not yet in the set $\{a_{1}, \ldots, a_{n}, b_{1}, \ldots, b_{n}\}$. It remains to show that the pair $(a_{n+1}, b_{n+1})$ is indeed good. For this, we distinguish the following possibilities for Henning's first move with starting values $(a_{n+1}, b_{n+1})$:
If Henning only reduces the pile with $b_{n+1}$ coins, he reaches a number of coins that is already in the set $\{a_{0}, a_{1}, \ldots, a_{n}, b_{0}, b_{1}, \ldots, b_{n}\}$. In any case, Paul can now, by reducing the pile with $a_{n+1}$ coins, reach a good pair, since $a_{n+1} > a_{k} \geq b_{k}$ for all $k \in \mathbb{N} \cup \{0\}$.
If Henning reduces both piles, the pile with originally $b_{n+1}$ coins is reduced to a number in $\{a_{0}, a_{1}, \ldots, a_{n}, b_{0}, b_{1}, \ldots, b_{n}\}$. If it is an $a_{k}$, Paul can of course reduce the other pile to $b_{k}$ coins because $a_{n+1} - x > b_{n+1} - x = a_{k} \geq b_{k}$. If it is a $b_{k}$, Paul can reduce the other pile to $a_{k}$ coins because $a_{k} = b_{k} + k < b_{k} + n + 1 = (b_{n+1} - x) + n + 1 = a_{n+1} - x$.
If Henning only reduces the pile with $a_{n+1}$ coins to $x$ coins, there are again several possibilities:
If $x \geq b_{n+1}$, Henning has reduced the difference between the two piles. Since $b_{n+1} > b_{k}$ for all $k \in \{0,1, \ldots, n\}$, Paul can reach the pair with this new difference by removing a suitable number of coins from both piles.
If $x < b_{n+1}$, then either $x = a_{k}$ or $x = b_{k}$ for some $k \leq n$. If $x = a_{k}$, then $b_{k} \leq a_{k} < b_{n+1}$, so Paul can reach the good pair $(a_{k}, b_{k})$ by reducing the pile with $b_{n+1}$ coins. If $x = b_{k}$, then we distinguish two cases: Either $a_{k} = b_{k} + k < b_{n+1}$; in this case, Paul reduces the pile with $b_{n+1}$ coins to reach the good pair $(a_{k}, b_{k})$, or $a_{k} = b_{k} + k > b_{n+1}$ (note that $a_{k} = b_{n+1}$ cannot occur by the construction of $b_{n+1}$). In this case, $b_{n+1} - x < a_{k} - x = a_{k} - b_{k} = k$. So the difference between $x$ and $b_{n+1}$ is less than $k$, and Paul can reach the good pair with this difference by removing a suitable number of coins.
These are all possible cases. Thus, we have shown that $(a_{n+1}, b_{n+1})$ is also good.

Now we use all these insights to show that the sequence $(m_{k})_{k \geq 1}$ can never become periodic:
Suppose the sequence $(m_{k})_{k \geq K}$ is periodic with period $c \geq 1$. We define $d = a_{K+c} - a_{K}$ and note (inductively) that $a_{k+nc} = a_{k} + n d$ holds for all $k \geq K$ and $n \in \mathbb{N}$. Furthermore, $d > c$, because otherwise, due to periodicity, every natural number greater than $K$ would be contained in $A$, and thus the set $B$ would be finite, which is obviously absurd. So there is an $n \in \mathbb{N}$ such that $n(d-c) \geq K$. For this $n$, however, we have:
$$b_{n d} = a_{n d} - n d = a_{n(d-c)}$$
This contradicts $A$ and $B$ being disjoint! Thus, we are done.

Solution:

As in the first solution, we show that $A^{(0)} := \{a \in \mathbb{N}_{0} \mid \exists 0 \leq b \leq a : (a, b) \text{ good}\} = \{a_{0}, a_{1}, \ldots\}$ (with $a_{0} < a_{1} < \ldots$) is infinite. Furthermore, we note that if $(a, b)$ and $(a', b')$ are good and additionally $a = a'$ or $b = b'$ or $a-b = a'-b'$, then $(a, b) = (a', b')$. This leads to the fact that for each $a_{k} \in A^{(0)}$ there is exactly one $b_{k} \in \mathbb{N}_{0}$ such that $(a_{k}, b_{k})$ is good; by definition of $A^{(0)}$, $a_{k} \geq b_{k}$. Furthermore, if we set $B^{(0)} := \{b_{0}, b_{1}, \ldots\}$, then $A^{(0)} \cap B^{(0)} = \{0\}$, since if $a_{k} = b_{l}$ with $k, l > 0$, the pairs $(a_{l}, a_{k})$ and $(b_{k}, a_{k})$ are good, but also $b_{k} < a_{k} = b_{l} < a_{l}$, contradiction. Now we show by strong induction that for all $k \geq 1$ the following holds:
(i) $\{0,1, \ldots, b_{k}\} \subset \{a_{0}, \ldots, a_{k}\} \cup \{b_{0}, \ldots, b_{k}\}$
(ii) $a_{k} - b_{k} = k$
(iii)
$$(a_{k}, b_{k}) = \begin{cases} (a_{k-1}, b_{k-1}) + (2,1) & \text{if } b_{k-1} + 1 \notin \{a_{0}, \ldots, a_{k-1}\} \\ (a_{k-1}, b_{k-1}) + (3,2) & \text{otherwise} \end{cases}$$
The statement holds for $k=1$ and $k=2$, so assume it holds for all $i \leq k$ with $k \geq 2$. Suppose there is a good pair $(a_{k}+1, b)$, then by (i) of the induction hypothesis $b > b_{k}$, since all values up to $b_{k}$ already appear in a good pair with a smaller other pile. But then $a_{k}+1-n \leq k$, which is a contradiction, since this difference is already occupied by a smaller good pair, by (ii) of the induction hypothesis. Now we distinguish cases.

Case 1: $b_{k}+1 \notin \{a_{0}, \ldots, a_{k}\}$
We show that $(a_{k}+2, b_{k}+1)$ is good, and thus $(a_{k+1}, b_{k+1}) = (a_{k}, b_{k}) + (2,1)$. Indeed, all $(a_{k}+2, b_{k}+1-m)$ are bad, since by (i) $b_{k}+1-m$ already appears in a good pair with a smaller other pile, $(a_{k}+2-m, b_{k}+1-m)$ is bad since $m=1$ is not possible by the above argument, and if for $m \geq 2$ the pair $(a_{k}+2-m, b_{k}+1-m)$ were good, we would necessarily have $(a_{k}+2-m, b_{k}+1-m) = (a_{l}, b_{l})$ for some $l \leq k$, which is not possible since $k+1 = (a_{k}+2-m)-(b_{k}+1-m) = a_{l}-b_{l} = l$. Finally, $(a_{k}+2-m, b_{k}+1)$ is also bad, since again $m=1$ is not possible, and if $(a_{k}+2-m, b_{k}+1)$ is good for $m \geq 2$, then $b_{k}+1$ cannot be the smaller pile since it could then have at most $b_{k}$ stones. But since $b_{k}+1 \leq b_{k}+k = a_{k}$, it follows that $b_{k}+1 \in \{a_{0}, \ldots, a_{k}\}$, which contradicts our assumption.

Case 2: $b_{k}+1 \in \{a_{0}, \ldots, a_{k}\}$
We first show that $a_{k+1} \geq a_{k}+3$. Suppose there is a good pair $(a_{k}+2, b)$. Since all values up to $b_{k}$ already appear in a good pair with a strictly smaller other pile, $b > b_{k}$ must hold. Since by assumption $b_{k}+1 \in \{a_{0}, \ldots, a_{k}\}$, $b = b_{k}+1$ is also not possible. Thus $a_{k}+2-b \leq a_{k}+2-(b_{k}+2) = k$, which is again a contradiction, since this difference is already occupied by a smaller good pair. Now we show that $(a_{k}+3, b_{k}+2)$ is good and thus $(a_{k+1}, b_{k+1}) = (a_{k}, b_{k}) + (3,2)$. Indeed, $(a_{k}+3, b_{k}+2-m)$ is bad since all values up to $b_{k}+1$ already appear in a smaller good pair, $(a_{k}+3-m, b_{k}+2-m)$ is bad since $m=1$ and $m=2$ were already excluded at the beginning of this case and at the beginning of the induction, and if $(a_{k}+3-m, b_{k}+2-m)$ is good with $m \geq 3$, then necessarily $(a_{k}+3-m, b_{k}+2-m) = (a_{l}, b_{l})$ for some $l \leq k$, which is a contradiction since $k+1 = (a_{k}+3-m)-(b_{k}+2-m) = a_{l}-b_{l} = l$. Finally, $(a_{k}+3-m, b_{k}+2)$ is also bad, since $m=1$ and $m=2$ were already excluded, and if $(a_{k}+3-m, b_{k}+2)$ is good with $m \geq 3$, then $b_{k}+2$ must be the larger pile, since otherwise it could have at most $b_{k}$ stones. Thus, since $b_{k}+2 \leq b_{k}+k \leq a_{k}$, $b_{k}+2 \in \{a_{0}, \ldots, a_{k}\}$, which contradicts our assumption $b_{k}+1 \in \{a_{0}, \ldots, a_{k}\}$, since by (iii) of the induction hypothesis the difference between two values from $\{a_{0}, \ldots, a_{k}\}$ cannot be 1. Thus, we have proved (iii) for $k+1$, from which (i) and (ii) follow directly. Additionally, from (i) it follows that $\mathbb{N}_{0} = A^{(0)} \cup B^{(0)}$. Calculating the first few values of the sequences $(a_{k})$ and $(b_{k})$, one conjectures that the following, somewhat more illustrative recursion formula holds:
$$(a_{k}, b_{k}) = \begin{cases} (a_{k-1}, b_{k-1}) + (2,1) & \text{if } k-1 \in \{a_{0}, \ldots, a_{k-1}\} \\ (a_{k-1}, b_{k-1}) + (3,2) & \text{otherwise} \end{cases}$$
To show this, we need the following intermediate result, which we prove by induction for all $k \geq 1$: apparently $b_{b_{k}} + 1 = a_{k}$ and $b_{b_{k}+1} = a_{k} + 1$. The two equations hold for $k=1$, so assume they hold for some $k \geq 1$. We make the same case distinction as before.

Case 1: $b_{k}+1 \notin \{a_{0}, \ldots, a_{k}\}$
We have $b_{k+1} = b_{k} + 1$ and thus $b_{b_{k+1}} + 1 = b_{b_{k}+1} + 1 = a_{k} + 1 + 1 = a_{k+1}$ by our induction hypothesis. Since in particular $b_{b_{k}+1} + 1 \in \{a_{0}, \ldots, a_{b_{k}+1}\}$, it follows from our already proven recursion formula that $b_{b_{k+1}+1} = b_{b_{k}+2} = b_{b_{k}+1} + 2 = a_{k} + 3 = a_{k+1} + 1$.

Case 2: $b_{k}+1 \in \{a_{0}, \ldots, a_{k}\}$
In this case, $b_{k+1} = b_{k} + 2$ and $a_{k+1} = a_{k} + 3$. By the induction hypothesis, $b_{b_{k}+1} + 1 = a_{k} + 2 < a_{k+1}$, and thus $b_{b_{k}+1} + 1 \notin \{a_{0}, \ldots, a_{b_{k}+1}\}$. It follows that $b_{b_{k+1}} + 1 = b_{b_{k}+2} + 1 = b_{b_{k}+1} + 1 + 1 = a_{k} + 1 + 1 + 1 = a_{k+1}$. Since in particular $b_{b_{k}+2} + 1 \in \{a_{0}, \ldots, a_{b_{k}+2}\}$, we also get $b_{b_{k+1}+1} = b_{b_{k}+3} = b_{b_{k}+2} + 2 = a_{k+1} + 1$. Thus, the two equations are proved.

Now we can show the following equivalence: $b_{k}+1 \in \{a_{0}, \ldots, a_{k}\} \Longleftrightarrow k \notin \{a_{0}, \ldots, a_{k}\}$. For if $b_{k}+1 = a_{l}$ then $l \geq 1$ and thus $b_{k}+1 = a_{l} = b_{b_{l}} + 1$ and thus $b_{k} = b_{b_{l}} \Longrightarrow k = b_{l} \Longrightarrow k \notin \{a_{0}, \ldots, a_{k}\}$. And if $k \notin \{a_{0}, \ldots, a_{k}\}$, then there is $l \geq 1$ with $k = b_{l}$ and thus $b_{k}+1 = b_{b_{l}} + 1 = a_{l} \in \{a_{0}, \ldots, a_{k}\}$. This equivalence leads directly to the more illustrative recursion formula. Now, if we define $s_{k} = |\{l \geq 0 \mid a_{l} < k\}|$, it follows that $a_{k} = 3(k - s_{k}) + 2 s_{k} = 3k - s_{k}$. Finally, we come to the actual proof.

Suppose there is a $K$ such that $(m_{k})_{k \geq K}$ is periodic with period $c \geq 1$. Set $A := a_{K+c} - a_{K}$, then from periodicity it follows that $a_{k+c} - a_{k} = A$ for all $k \geq K$. We also note that if $k \geq a_{K}$, then $|\{l \geq 0 \mid k \leq a_{l} < k+A\}| = c$, so $s_{k+A} = s_{k} + c$ for all $k \geq a_{K}$. Now let $k \geq \max\{K, a_{K}\}$, then we get
$$a_{k} + A^{2} = a_{k + cA} = 3(k + cA) - s_{k + cA} = 3(k + cA) - s_{k} - c^{2}$$
and thus
$$A^{2} - 3cA + c^{2} = 3k - a_{k} - s_{k} = 0$$
From this, we finally obtain that $\frac{A}{c} \in \{\varphi^{-2}, \varphi^{2}\}$, where $\varphi$ is the golden ratio. This is a contradiction, since $\varphi^{-2}$ and $\varphi^{2}$ are irrational.