两场比赛

4

两场比赛

I.M.亚格洛姆

在这篇文章中我们向您介绍游戏“他”
和“Izyanshizians”。 “nim”和“izianshiz”都是中国民间游戏； “Izyanshiztsy”翻译过来的意思是“选择棋子”（当然，在游戏中用火柴代替棋子并不会改变其本质）。随后，这些游戏渗透到欧洲；一度，“nim”游戏在西欧流行。

5

这是这个游戏的规则。

游戏“他”
桌子上有三堆火柴。两个查拉亚齐轮流从这些堆中取出火柴，并且一次查拉亚齐可以从一堆（必须只能从一堆！）中取出任意数量的火柴。我们将忍受并引用最后一个收回的人。

游戏“Izyanshiztsy”
桌子上有两堆火柴。两个查拉亚齐轮流从这些堆中取出火柴，并且一次查拉亚齐可以从一堆中取出任意数量的火柴，或者从两堆中取出相同数量（但任意数量！）的火柴。我们将忍受并引用最后一个收回的人。

任务是确定初学者在哪些初始位置（即每堆比赛的数量）可以获胜，哪些不能获胜，并指出正确（双赢）获胜的方法。

对于实际玩家来说，在黑板上玩它或izyanshiztsy 非常方便 - 无需任何比赛，但手上有粉笔和三脚架。在棋盘上，您可以绘制三行以棋盘右边缘结束的字段，以及三个棋子 - 每行字段中一个（图1）。轮到的每个玩家都会摧毁一个棋子，并将其“重播”到右侧任意数量的区域（这里我们谈论的是与他一起玩）；胜利者是迈出最后一步的人。您可以用同样的方式玩 Izyanshizi - 只是现在游戏板包含两行

图 1.

图 2.

7

不幸的是，这里也没有制定该表的具体法律。

表一和表二是否可以写成不同的形式？

我们无法理解表一和表二是如何编制的，在第一种情况下由表冠形成，在第二种情况下由两行数字形成。现在让我们思考一下我们遭遇失败的可能原因。

我们已经说过，表一和表二是数值表；它们由一系列数字组成。当然，我们用通常接受的十进制数字系统，以通常的方式写下了这些表中出现的数字；例如，构成表 II 最后一列的数字 24 和 39 将为：“2 个十和 4 个单位”和“3 个十和 9 个单位”。然而，十进制数字系统本身，其起源与一个人手上有 10 个手指的随机情况有关，与我们正在考虑的游戏没有任何关系；因此，尝试以不同的方式编写表格似乎是一种简化。

本文的进一步内容与《数字系统》一文（«Kvant»第6期）有关。我们需要本文中的以下内容。

有许多使用少量符号（数字）书写正数的系统。位置数字系统（更准确地说，用于书写数字的位置系统）的构造如下。指定了某个基础或关键数字系统，它表示无限可能的整数序列：

$$1 = q_0 < q_1 < q_2 < q_3 \dots$$

之后，每个数字 $N$ 都表示为我们的基数的总和，并采用某些整数系数：

$$N = a_m q_m + a_{m-1} q_{m-1} + \dots + a_2 q_2 + a_1 q_1 + a_0 q_0;$$

这个表达式是这样写的：

$$N = a_m a_{m-1} \dots a_2 a_1 a_0,$$

其中$a_m, a_{m-1}, \dots$是数字$N$的“数字”。

例如，如果基数系统是：

$$1, 2, 3, 5, 7, 11, 13, 17, 19, 23, \dots$$

那么数字27写成如下：

$$27 = 1 \cdot 23 + 0 \cdot 19 + 0 \cdot 17 + 0 \cdot 13 + 0 \cdot 11 + 0 \cdot 7 + 0 \cdot 5 + 1 \cdot 3 + 0 \cdot 2 + 1 \cdot 1 = \text{«1000000101»}.$$

在这种情况下，以 (*) 为基数的数系中任何数字 $N$ 表示法中的第 $k$ 位 $a_k$ 始终小于相对的 $q_k + 1/q_k$。

如果数系的基础具有以下形式：

$$1 = q^0, q = q^1, q^2, q^3, q^4, \dots,$$

其中$q$是某个整数，则该数系称为“q位”，其中所有数字都由数$q$的幂之和表示，并且数$N$的表示法中的所有数字都小于$q$（在普遍接受的十进制数系中小于10）。

8

所有书写整数的系统中最简单的是双数系统，其中所有数字都由 2 的幂和表示。如果我们使用这个数系统，那么我们的表 I 和表 II 将采用完全不同的形式（双数系统中的数字将用红色数字书写）：

表Ia

| №№ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| :— | :— | :— | :— | :— | :— | :— | :— | :— | :— | :— | :— | :— | :— | :— | :— |
| a | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 10 | 0 | 11 | 10 | 1 | 0 | 0 | 1 |
| b | 1 | 10 | 10 | 11 | 100 | 100 | 101 | 100 | 110 | 100 | 101 | 110 | 111 | 1000 | 1000 |
| c | 1 | 10 | 11 | 11 | 100 | 101 | 101 | 110 | 110 | 111 | 111 | 111 | 111 | 1000 | 1001 |

表IIa

| №№ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| :— | :— | :— | :— | :— | :— | :— | :— | :— |
| a | 1 | 11 | 100 | 110 | 1000 | 1001 | 1011 | 1011 |
| b | 10 | 101 | 111 | 1010 | 1101 | 1111 | 1111 | 1010 |

| №№ | 110 | 1000 | 10001 | 10011 | 10101 | 1101 | 1111 | 10101 | 1010 | 1010 | 1010 | 1010 | 1010 |
| :— | :— | :— | :— | :— | :— | :— | :— | :— | :— | :— | :— | :— | :— | :— |
| 1110 | 10000 | 10001 | 10011 | 10101 | 1101 | 1111 | 1011 | 1011 | 1011 | 1011 | 1011 | 1011 | 1011 |

**仔细研究表Ia，我们可以在其中看到该模式的完整定义：是的，当然，cerem“nim”中的析取位置（a，b，c）是.me位置，意味着数字a，b，c cemena的双重表示法中的数字之前的数字之和（即等于0或2）！然而，表IIa结果更加阴险：它并不比表II好，并且不能从中辨别出失败对(a，b)的组成的明确模式。

但为什么双数制应该成为寻找千石双赢体系的关键呢？确实，我们看到这个系统似乎有助于发展 nim 游戏的理论：但是千世子是一个完全不同的游戏，打开一扇门的钥匙根本不需要适合另一扇门。是否有可能以不同的方式重写表II：也许是不同的记录图像的系统

这个数字系统是否更能说明其结构？

仔细研究表 II，我们可以注意到其中经常出现斐波那契数列，例如表的第 1、2、5 和 13 列 *)。反过来，这可能会让我们思考尝试在“斐波那契数字系统”中编写表二是否明智，其中所有数字都由斐波那契数列中的数字之和表示（我们将用蓝色数字书写该数字系统中的数字）。例如，斐波那契数列中的数字 100

*) 斐波那契数列是以 1 和 2 开始的数字序列，然后根据以下规律构建：斐波那契数列中的哪个数字等于前两个数字之和。它的第一项是： 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, … N. N. Vorobyov 的一本很好的小册子“斐波那契数”（M.，“Hayka”，第 3 版，1969 年）专门介绍了斐波那契数。

10

对于仪式中的上述条件a)和6))，“it”是.me，而不是位置(a,b,c)，对于水泥的所有数字，其与双数系统中数字a、b、c记录中的一位数字对应的所有数字之和。

定理二。仪式中的程序“izanyitsy”是.me，而不是位置（a，b），其中a，以斐波那契数系书写，以整数个零结尾，而数字b是从数字a获得的，我们在末尾再添加一个零。

然后呃。从定理 I 和 II 可以看出，“nim”和“izanyitsy”这两种游戏在某种意义上都对初学者有利：按位置划分，初学者有不少输家（见表 I 和 II），也就是说，它们比所有其他（初学者获胜）位置要少得多。

这些定理的证明构成了下面练习的内容。第 60 页给出了这些问题的答案（但是，请尝试自己找到解决方案）。我们建议您首先处理练习 1-4，因为练习 5-7 更加困难。

练习

1. 证明如果“他”在游戏中的位置（a，b，c）不是败局，即不满足定理一的表述所规定的条件，那么玩家可以通过自己的走法使其成为败局。

2. 证明如果“nim”博弈中的位置（a，b，c）不是败局，即不满足定理一的表述所规定的条件，那么玩家可以通过一步操作将其变为败局。

3. 如果火柴堆的数量是任何预定的数字 n ≥ 2，则在游戏“nim”中指示正确的游戏（我们让正确游戏的其余部分保持不变）。 n = 2 的情况下双赢博弈的证据是什么？

4. 描述游戏“nim”中的失败位置 (a, b, c)，将数字 a、b、c 写成四进制而不是双进制（也就是说，以 a = aₙaₙ₋₁…a2a₁a₀ = aₙ4ⁿ + aₙ₋₁4ⁿ⁻1 + … + a24² 的形式表示数字 a） + a₁4 + a₀；这里 0 ≤ aᵢ ≤ 3 对于所有 i = n, n − 1,…, 2, 1, 0 *))

5. 证明对于任意正整数p，赔率博弈中存在且仅有一个失败位置（a，b）（即满足定理二条件的位置），使得b − a = p。检查表 II 中列出的前 15 个亏损头寸。

6. 证明如果“Izyanytsy”游戏中的位置 (b, a) 不满足定理 II 的条件，则自己走棋的玩家要么立即获胜，要么导致该位置失败。

7. 证明如果“Izyanytsy”游戏中的位置 (a, b) 正在失败，那么在玩家进行任何移动之后，情况将不再如此。

8. 如果堆数为奇数，请在“Izyanytsy”仪式中指出正确的游戏（玩家每次移动都有权从每一堆中取出任意数量的火柴，或者同等地 - 也可以是任意数量！ - 从所有堆中取出火柴）。

问题。如果桩数为四，请指出“Izyanytsy”仪式中的正确游戏。

我想警告读者，作者不知道所提出问题的解决方案。

*) 数字上方的行表示这是一个以数字 aₙaₙ₋₁…a2a₁a₀ 书写的数字，而不是数字的乘积。