TOAD 37 - Zeroise Me

似乎 Matrix67 大大已经翻译过了。

Problem

一个长度为 \(n\) 的 0/1 串，A/B 俩人博弈。每次操作如下：

1. 如果当前串首是 1 ，则放一个 0/1 到串尾，由 A 决定
2. 如果当前串首是 0 ，则放一个 0/1 到串尾，由 B 决定
3. 删除串首，重复以上过程

如果有限步内这个串全是 0 ，则 A 获胜，否则 B 获胜。

问什么情况下 A 必胜。

Solution

任一情况下 A 都必胜。

A 的方案如下：我们把整个串看成是一个大的二进制数。我们称连续操作 \(n\) 次为一轮操作。如果我们保证任意一轮操作后，二进制数一定会增加，那么总有一轮过后整个串会全是 1 。这个时候全部都是 A 操作，全部设为 0 即可。

如何保证二进制数一定会增加呢？A 的策略为，在这一轮中，如果 B 已经将一个 0 变为 1 了，则保持这个 1 不变，否则把 1 变为 0 。显然，B 至少将一个 0 变为 1 ，否则 A 就赢了。只要 B 将一个 0 变为 1，则整个串的二进制数一定会增加。