Problem 939
Partisan Nim
Two players A and B are playing a variant of Nim.
At the beginning, there are several piles of stones. Each pile is either at the side of A or at the side of B. The piles are unordered.
They make moves in turn. At a player’s turn, the player can
- either choose a pile on the opponent’s side and remove one stone from that pile;
- or choose a pile on their own side and remove the whole pile.
The winner is the player who removes the last stone.
Let $E(N)$ be the number of initial settings with at most $N$ stones such that, whoever plays first, A always has a winning strategy.
For example $E(4) = 9$; the settings are:
| Nr. | Piles at the side of A | Piles at the side of B |
|---|---|---|
| 1 | $4$ | none |
| 2 | $1, 3$ | none |
| 3 | $2, 2$ | none |
| 4 | $1, 1, 2$ | none |
| 5 | $3$ | $1$ |
| 6 | $1, 2$ | $1$ |
| 7 | $2$ | $1, 1$ |
| 8 | $3$ | none |
| 9 | $2$ | none |
Find $E(5000) \bmod 1234567891$.
偏心的取石子游戏
两名玩家A和B正在玩一种变体取石子游戏。
游戏开始时，有数堆石子，每一堆石子要么属于A，要么属于B；石子堆之间是无序的。
两名玩家轮流行动。轮到任一玩家时，该玩家可以
- 选择属于对手的一堆石子，并从中移除一枚石子；或者
- 选择属于自己的一堆石子，并移除整堆。
移除最后一枚石子的玩家获胜。
令$E(N)$为最多有$N$枚石子，且无论谁先行动A总是有必胜策略的初始局面数量。
例如，$E(4) = 9$，这些初始局面分别是：
| 编号 | 属于A的石子堆 | 属于B的石子堆 |
|---|---|---|
| 1 | $4$ | 无 |
| 2 | $1, 3$ | 无 |
| 3 | $2, 2$ | 无 |
| 4 | $1, 1, 2$ | 无 |
| 5 | $3$ | $1$ |
| 6 | $1, 2$ | $1$ |
| 7 | $2$ | $1, 1$ |
| 8 | $3$ | 无 |
| 9 | $2$ | 无 |
求$E(5000) \bmod 1234567891$。