Zugzwang 在国际象棋、数学和披萨中的秘密

大多数让两名球员或球队相互对抗的游戏都需要其中一个人进行第一次比赛。这导致了内在的不对称性，问题就出现了：你应该先走还是第二走？

大多数人本能地想先走，这种直觉通常得到证实。在国际象棋或网球等常见的两人游戏中，“赢得折腾”并先走是一种真正的优势，即使是适度的优势。但有时让对手先出手对你有利。

在我们二月份的洞察谜题中，我们提出了四种不同的情况，在这些情况下，与直觉相反，搬家的义务是一个严重且通常是决定性的劣势。在国际象棋中，这被称为 zugzwang——一个德语单词，意思是“强制移动”。让我们看看 zugzwang 的奇异魔法是如何在我们的四个场景中实现的。

谜题 1：国际象棋

下面棋盘上的位置是在 1971 年世界锦标赛候选人比赛的第二场比赛中，美国大师鲍比·菲舍尔下白棋和苏联特级大师马克·泰马诺夫下黑棋。轮到黑方下，可惜黑方在zugzwang，必输。我们的任务是解释如何。

如果我们比较次要棋子，白棋有象，黑棋有马。这些都不足以迫使胜利。但白棋也有一个棋子，可以前进到棋盘的顶端，成为王后。如果发生这种情况，白色很容易获胜。所以黑方的任务很明确：泰马诺夫必须抓住白兵，即使这意味着要牺牲他的马来这样做。这将导致平局，这是黑色在这里可以做到的最好的。

起初，似乎黑马处于捕获白棋的好位置。马受黑王保护，控制h7格，白兵必须通过该格才能晋级。

唉，现在zugzwang的“移动强迫症”抬起了丑陋的头。虽然 Taimanov 会满足于让他的马留在 g5 上，但他处于不幸的境地，不得不移动他的国王或马。如果他移动他的国王，它就不能再保护骑士了，骑士就会灭亡，让棋子自由前进。另一方面，如果他将马移动到唯一的安全格f3，然后白方将他的棋子推到h6，那么真正的黑方可以在随后的移动中将马移回g5。这可以防止 Fischer 立即将他的棋子推进到 h7。但是现在白方可以拿出下棋的秘密武器：他可以做一个“等待”着法，将他的国王滑到g6。再一次，黑棋必须走，现在泰马诺夫真的没有可行的选择了。

如果黑移动他的国王，他的马就会倒下。如果他将马移动到 f3，白方的兵前进到 h7，游戏就结束了。 （如果他将他的马移动到其他任何地方，白色的主教或国王将抓住它，它也结束了。）这就是 zugzwang 的力量。

不用说，费舍尔赢得了比赛。然后他在第四场比赛中将泰马诺夫困在一个更复杂的曲折中，最终以6-0横扫比赛。费舍尔在 1972 年击败苏联特级大师鲍里斯·斯帕斯基（Boris Spassky）成为被称为“ 世纪比赛”的世界冠军之前，击败了另外两位顶级大师。

几位读者描述了这个问题的解决方案。

谜题 2：尼姆

在古代游戏Nim的这种变体中，两个玩家 A 和 B 玩一个减法游戏，B 可以选择一个起始数字，每个玩家依次从中减去一个小数字，直到他们达到零。在每一轮中，玩家必须至少减去 1，最多比当前数字的十位多 1。因此，如果当前数字在 90 到 99 之间，他们可以减去 10 以内的任何数字；如果是 80 到 89，他们可以减去 1 到 9，依此类推。最后，当剩余数在 1 到 9 之间时，他们每回合只能减 1。 A 先走，B 可以在 90 到 99 之间选择一个起始数字。坚持做最后一个减法的玩家输了。

问题：B应该选择什么起始编号？你能列出整个zugzwang梯子吗？

这个谜题由读者Seth Cohen和sunil nandella 解决。我只能引用 Seth Cohen 的出色解释：

问题：你能描述一下导致互惠 zugzwang 位置（下一个玩家输掉）的最短可能的 Sim 游戏吗？按顺序列出游戏中的动作。

这是一个 Sim 位置，在该位置中，9 步即可达到倒数 zugzwang 位置。

可以产生这个位置的移动指令是AB , BE , AC , CE , AD , DE , AF , FE , AE 。剩下六个未着色的边缘：BC、BD、BF、CD、CF 和 DF。将它们中的任何一个着色为红色或蓝色都会强制三角形的所有边具有相同的颜色，如下表所示。

因此，下一个必须移动的玩家（在本例中为蓝色玩家）将处于 zugzwang，并且会输。要了解我们是如何到达这个位置的，请考虑由四个点 ABCE 形成的四边形。它有两个连续的红色边缘 AB 和 AC，以及两个连续的蓝色边缘 BE 和 CE。所以无论边 BC（四边形的对角线）是什么颜色，它都会完成一个相同颜色的三角形。您可以将这样一组缺少边缘的四个点视为单个“zugzwang 单元”。在这个位置有六个这样的单位，每一个都注定了六个无色边缘之一。

由于打法不完善，蓝方在比赛初期就达到了这种情况。正如我在拼图专栏中提到的，无论第一个玩家做什么，Sim 中的第二个玩家总是可以使用获胜策略。策略是避免创建 zugzwang 四边形——除了两个没有着色的公共边。图中正好有“6 选择 2”（或 15 条）边，所以第 15 步（最后一步）总是落到第一个玩家身上。 Ramsey 理论告诉我们，有六个点将至少有两个三角形的边缘颜色相同。通过完美的游戏，第二个玩家应该能够将单色三角形的创建推迟到最后一步。这将诱使第一个玩家用最后一条边形成两个单色三角形。

读者sunil nandella描述并绘制了这样一个完美游戏的位置，其中倒数的 zugzwang 情况发生在第 15 步，导致第一个玩家不可避免地产生两个必需的单色三角形而输掉。 nandella 解中的两个 zugzwang 四边形是 BCEF 和 ABDE，它们都以 BE 作为最后一个无色边。

谜题 4：披萨

两个玩家，A 和 B，分享一个披萨。 A 可以选择第一片，B 可以切披萨。 B 必须将比萨饼切成楔形放射状切片，制作任意数量的切片，但大小不必相同。 A 可以选择任何第一个切片。之后 B 和 A 轮流吃一片，总是选择与比萨饼的开口部分相邻的两片中的一片。 A 和 B 都尽最大努力获得尽可能多的比萨饼。

问题：

1. B 如何切披萨，使得在切完所有薄片后，B 的披萨比 A 多？给出可能发生这种情况的最小可能切片数，以及每个切片的相对大小。
2. B 可以获得的比萨饼的最大比例是多少？
3. 您能否指定所有可能无法实现此结果的切片数量？

在我描述解决方案之前，让我们回顾一下可以引导我们找到答案的一些启发式想法。正如Jack Latta所指出的，如果披萨片的数量是偶数，B 永远无法获得更大的比萨饼部分。为了理解为什么，让我们假设比萨有八片，编号为 1 到 8。现在比萨在概念上可以分为两部分：奇数切片O （切片 1、3、5、7）和偶数切片E （切片 2、4、6、8）。玩家 A 可以确保他得到E或O ，以较大者为准。如果O是较大的部分，A 可以从切片 1 开始，让 B 选择切片 2 或 8；然后，无论 B 选择哪个切片，A 都可以继续选择暴露的奇数切片（下一轮为 3 或 7）。这总是给 B 留下偶数选项。相反，如果E较大，则 A 可以通过获得所有偶数切片来获胜。如果两个部分完全相同，A 可以选择奇数或偶数，仍然拒绝 B 的大部分比萨饼。所以我们寻找的披萨必须有奇数片。

再次，zugzwang 梯子（我将其称为 z 梯子）的概念开始发挥作用。正如我在谜题中所描述的，如果你有一排奇数片，大小交替为 1 和 3，那么先走的玩家必须“打开”梯子，将所有较大的棋子让给第二个玩家，第二个玩家将因此赢。

困难在于，对于圆形披萨，A 可以先挑一大块。那么z-ladder会发生什么？让我们考虑一下当比萨饼由单个七片 z 梯形图 1、3、1、3、1、3、1 组成时会发生什么，如下图所示，其中的切片编号为灰色，尺寸为棕色。

区分切片 4（我们称为中间切片）和切片 2 和 6（即侧切片）是很有用的。如果 A 取中间的大切片 4，那么我们剩下两个切片大小为 1、3、1（切片编号 1-3 和 5-7）的连接 z 梯。 B 必须打开其中一个（她可以决定哪一个），取第 3 或第 5 块，将另一大块让给 A。打开的梯子用完后，轮到 A，他有义务打开最后一个梯子，将最后一个大块割让给 B。所以在这种情况下，A 得到两个大块，B 得到一个。另一方面，如果 A 选择一个大的侧面切片（切片 2 或 6），那么我们就剩下一个 5 切片的 z 梯和一个小块，B 可以拿走，迫使 A 打开五片梯子，然后给 B 两片大片。在五片 z 梯披萨的情况下，两个大片都是侧片，A 和 B 各得到一个大片。

我们还没有解决方案，但我们已经收集了一些可以引导我们实现目标的见解。这些都是：

洞察一：披萨的块数必须是奇数。

洞见 2：一个 Z 形梯不起作用。基于洞察 1，以及 z 梯具有奇数个切片的事实，我们需要至少三个 z 梯串在一起。

洞见3：你只能看大片。 B 必须得到更多。

洞见 4：虽然 A 在 z 梯中占据了第一个大切片的优势，但他需要占据中间的大切片，否则他的优势就失去了。如果没有中间大切片（如在具有两个和四个大切片的 5 或 9 切片 z 梯中），则共享大切片。

洞见5：当剩下两个z-ladder时，下一个走的有决定打开哪个梯子的优势，迫使另一个玩家打开最后一个。在一个奇数块的比萨饼中，拥有这个关键选择的玩家将永远是 B。这个洞察力是金！

读者witzar提出了一个出色的 21 层解决方案，由三个长度为 5、7 和 9 层的 z 梯子组成，很好地说明了这些见解。比萨饼有九大片，梯子分别有两片、三片和四片。在下图中，三个 z 阶梯以不同的颜色显示。

在接下来的内容中，请注意，因为 A 拿下第一个切片，之后玩家交替进行，所以 A 总是在奇数轮转，B 在偶数轮转。

如果 A 从 5 片 z 梯中取出他的第一个大片，两名玩家将这两个大片分开，然后 B 可以在第 6 回合打开七片梯，给 A 三个大片，而 B 得到四个大片最后一个九层梯子的切片，A 被迫在第 13 回合打开。B 以 5 个大切片对抗 A 的 4 个。

如果 A 的第一个切片是七层阶梯的中间大切片，则 A 获得该阶梯的三个大切片中的两个。然后 B 在第 8 回合打开 5 片梯子，将其两个大片割让给 A，同时再次抓住所有 9 片梯子的大片 – 和以前一样，A 被迫在第 13 回合打开这个梯子。B 再次获胜五个大片到 A 的四个。

如果 A 的第一个切片是九层阶梯的中央大切片之一，则 A 和 B 将平分该阶梯的四个大切片，每人得到两个。发生这种情况是因为在第 5 回合，A 必须将梯子左侧的 5 片梯子打开给 B。然后，和以前一样，B 在第一个梯子完成后打开较小的 5 片梯子，这次是在第 10 回合. 然后她得到了最后一个七层梯子中的所有大块，A 被迫在第 15 回合打开。再一次，B 得到五个大块，而 A 是四个。

请注意，如果 A 在他的第一轮中选择一小块，他只会立即给 B 第一个 z-ladder 的大块，而不会改变 B 在剩下两个 z-ladder 时的战略优势。 A 的结果最终与上述情况一样糟糕，甚至更糟。如果 A 没有一直走到梯子的尽头，而是跳到未打开的梯子，也会发生同样的事情。总之，A从一开始就处于zugzwang，没有办法取胜。

很明显，如果只有大片很重要，5/9 是 B 可以获得的这种比萨的最大比例。这假设小片非常小，大片是小片的三倍多，并且 A 发挥最佳。因此，九分之五是我们第二个问题的答案。

事实证明，允许 B 获胜的最小切片数是 15，这就是我们第一个问题的答案。这个披萨由三个 zugzwang 梯子组成，每个梯子有五片，有两种大片：大 ( l ) 和特大 ( L )。此披萨中切片大小的通用模板是： s, l, s, l, s, s, L, s, L, s, s, l, s, L, s ，其中s代表小切片（如图所示）图中标有三个五层 Z 形梯子）。实际这样的比萨饼的 21 片的可能大小可能是：1、3、1、3、1、1、6、1、6、1、1、3、1、6、1。你可以玩这样一个比萨饼，并验证无论 A 先选择哪个切片，B 都获得了较大的部分，方法是确保她将在最后获得其他两个 z 梯中较重的大切片或超大切片。

对于这样的披萨，B 将得到两个超大L切片和一个l切片或一个L和三个l切片，这取决于 A 在第 3 回合所做的事情。当 B 都可能时， l和L之间的最佳比例发生上述收入相等，即 2 L + l = L + 3 l或L = 2 l 。 B 的最大份量为 (2 L + l )/(3 L + 3 l )，如前所述，为 5/9。事实证明，假设 A 发挥最佳，任何切片的排列都不会让 B 得到超过九分之五的比萨饼。

您可以在任何 z 梯之间用偶数个额外的小切片填充上述 15 片披萨，因此上述解决方案可以推广到具有 15 片以上任何奇数片的披萨。所以，我们第三个的答案问题是，如果比萨饼的片数为偶数，或者小于 15 的奇数片，B 就无法获胜。

这个问题由达特茅斯数学家和美食拼图大师彼得温克勒推广。在这里可以找到对这个问题和其他比萨分享问题的正式处理。

祝贺 witzar 出色地解决了这个困难的披萨 zugzwang 问题，并获得了本月的洞察奖。感谢所有做出贡献的人。

很快见，了解新见解。