Tower Breakers - 带除数的 nim 游戏变体

Question

我遇到过一款名为 Tower Breakers 的游戏，它似乎是nim 游戏的变体。

• 有两个玩家，玩家 1 和玩家 2。
• 最初有n塔，每个塔的高度为m，均为n正m整数。
• 玩家 1 开始，然后他们轮流移动。
• 在每一回合中，玩家可以选择一座高度的塔x > 1，并将其高度降低到一个正整数y，其中1 <= y < x和y整除x。
• 如果当前玩家无法采取任何行动，则输掉游戏。

有什么制胜策略吗？如果一开始塔的高度不相等怎么办？

Answer 1

这是塔破坏者（等高）的答案。

回答

• 如果 M 为 1，则第二个玩家获胜。
• 如果 N 为偶数(N % 2 == 0)且 M 不为 1，则第二个玩家获胜。
• 如果 N 为奇数(N % 2 == 1)且 M 不为 1，则第一个玩家获胜。

这是我的 C++ 代码。（已被接受）

#include <bits/stdc++.h>
using namespace std;
int Q, N, M;
int main() {
    cin >> Q;
    while(Q--) {
        cin >> N >> M;
        if(M == 1 || N % 2 == 0) cout << 2 << endl;
        else cout << 1 << endl;
    }
}

为什么它是正确的？

• 如果 M 为 1，很明显第二个玩家会获胜，因为第一个玩家无法移动。
• 如果N是偶数，第二个玩家可以对第一个玩家进行相同的操作。例如，如果第一个玩家移动{4, 4, 4, 4} -> {2, 4, 4, 4}，第二个玩家可以移动{2, 4, 4, 4} -> {2, 2, 4, 4}。最后第二个玩家可以做出{1, 1, 1, ..., 1}，所以第二个玩家可以获胜。
• 如果N是奇数，第一个玩家可以将第一个塔的高度降低到1，这样你就可以返回到“N是偶数”的情况。所以，你可以证明第一个玩家获胜。
• 所以，答案是正确的。

Answer 2

\n

一般情况

\n

这确实可以像nim 游戏一样解决，但使用不同的 nimber 定义。

\n

在原版游戏中，塔的数量简单地定义为其高度。

\n

T在这个变体中，高度为 的塔的数量h(T) = x = p\xe2\x82\x81\xcb\xa2\xc2\xb9 \xe2\x80\xa6 p\xe2\x82\x96\xcb\xa2\xe1\xb5\x8f，带有p\xe1\xb5\xa2素数，是

\n

n(T) = s\xe2\x82\x81 + \xe2\x80\xa6 + s\xe2\x82\x96\n

\n

n塔列表的数量L = (T\xe2\x82\x81, \xe2\x80\xa6, T\xe2\x82\x99)是通常的

\n

n(L) = n(T\xe2\x82\x81) \xe2\x8a\x95 \xe2\x80\xa6 \xe2\x8a\x95 n(T\xe2\x82\x99)\n

\n

如果你的回合开始时数字为 0，假设其他玩家表现完美，你将输掉你所做的一切。

\n

否则，你只需要做一个使数字变为零的动作。

\n

你可以这样做，因为如果n(L) > 0有一座塔，让我们在不失泛化的情况下假设它是T\xe2\x82\x99，这样n(T\xe2\x82\x99) \xe2\x8a\x95 n(L) < n(L)。

\n

这样的塔是存在的：最左边的位n(L)是1，那是因为有些塔T\xe2\x82\x99在该位位置有一个 1。你是否n(T\xe2\x82\x99) \xe2\x8a\x95 n(L)杀死了 1 并且不改变 的更重要的位，n(T\xe2\x82\x99)因为它是 的最左边的位n(L)。所以也n(T\xe2\x82\x99) \xe2\x8a\x95 n(L)比较小。

\n

那么你只需要修改T\xe2\x82\x99为T\xe2\x82\x99\'这样n(T\xe2\x82\x99\') = n(T\xe2\x82\x99) \xe2\x8a\x95 n(L)，从而

\n

n(L\') = n(T\xe2\x82\x81) \xe2\x8a\x95 \xe2\x80\xa6 \xe2\x8a\x95 n(T\xe2\x82\x99\') = n(T\xe2\x82\x81) \xe2\x8a\x95 \xe2\x80\xa6 \xe2\x8a\x95 n(T\xe2\x82\x99) \xe2\x8a\x95 n(L) = n(L) \xe2\x8a\x95 n(L) = 0\n

\n

这种移动总是可能的，例如将高度降低到x\' = p\xe2\x82\x81\xcb\xa2\xc2\xb9 \xe2\x80\xa6 p\xe2\x82\x97\xe2\x82\x8b\xe2\x82\x81\xcb\xa2\xcb\xa1\xe2\x81\xbb\xc2\xb9 p\xe2\x82\x97\xe1\xb5\x88、l <= k和0 < d <= s\xe2\x82\x97，这样s\xe2\x82\x81 + \xe2\x80\xa6 + s\xe2\x82\x97\xe2\x82\x8b\xe2\x82\x81 + d = n(T\xe2\x82\x99) \xe2\x8a\x95 n(L)。按结构x\'划分，因此它们是不同的。xx\' < x

\n

一旦数字为零，无论其他玩家做什么，都会影响该塔的数字，然后总异或n(L)将不再为零。然后你重复同样的策略。

\n

特殊案例

\n

在所有塔具有相同高度的特殊情况下，

\n

\n
• 如果有偶数个塔或高度为1的塔，则总数将为零，因此如果玩得最佳，玩家2将获胜。
\n
• 否则，总人数将不为零，因此如果发挥最佳，玩家 1 将获胜。
\n

\n

事实上，这可以在不使用数字的情况下显示：

\n

\n

• 如果塔的数量为偶数，玩家 2 可以将它们分成两两。他想要保持的不变量是每对中的两座塔具有相同的高度。每当玩家 1 采取行动时，这个不变量就会被破坏。然后玩家 2 只需要对另一座塔进行相同的移动（这将是有效的移动，否则玩家 1 无法完成）。最终，所有塔都会达到高度 1，玩家 2 将获胜。

  \n
\n

• 如果有奇数个塔（高度 > 1），玩家 1 可以将最后一个塔的高度降低到 1。实际上，这就像消除该塔。现在轮到玩家 2 了，但可玩的塔的数量将是偶数。所以前面的情况适用，玩家 1 将获胜。

  \n
\n

\n

玩

\n

您可以玩以下片段：

\n

\r\n

\r\n

function nimber(num) {\n  var n = 0;\n  for (var i=2; i<=num; ++i)\n    while(num % i == 0) {\n      ++n;\n      num /= i;\n    }\n  return n;\n}\nfunction change(tower, newHeight, oldHeight, txt) {\n  tower.textContent = newHeight;\n  totalNimber ^= tower.dataset.nimber;\n  tower.dataset.nimber = nimber(newHeight);\n  totalNimber ^= tower.dataset.nimber;\n  log.textContent += "    " + txt + " the height of the " + tower.getAttribute(\'data-index\')\n                     + "-th tower from " + oldHeight + " to " + newHeight + ".\\n";\n  if (newHeight == 1) tower.removeEventListener(\'click\', playerMove);\n}\nfunction end(txt) {\n  log.textContent += "    " + txt;\n  playerMove = Function.prototype;\n}\nfunction prePlayerMove() {\n  log.textContent += "Your turn. nimber = " + totalNimber + ".\\n";\n  for (var i=0; i<n; ++i) {\n    var height = +towers.children[i].textContent;\n    if (height != 1) return;\n  }\n  end("You lose");\n}\nfunction playerMove() {\n  var oldHeight = +this.textContent, newHeight;\n  while(!newHeight || newHeight <= 0 || oldHeight%newHeight || newHeight == oldHeight)\n    newHeight = +prompt("Current tower height is " + oldHeight + ". Enter new height");\n  change(this, newHeight, oldHeight, "You reduce");\n  pcMove();\n}\nfunction pcMove() {\n  log.textContent += "PC\'s turn (nimber = " + totalNimber + ").\\n";\n  if (totalNimber == 0) { // Oh shit.\n    for (var i=0; i<n; ++i) {\n      var oldHeight = +towers.children[i].textContent;\n      if (oldHeight != 1)\n        for (var j=2; j<=oldHeight; ++j)\n          if (oldHeight % j == 0) {\n            var newHeight = oldHeight / j;\n            change(towers.children[i], newHeight, oldHeight, "PC reduces");\n            prePlayerMove();\n            return;\n          }\n    }\n    end("PC loses");\n  } else {\n    for (var i=0; i<n; ++i) {\n      var tower = towers.children[i];\n      var objective = tower.dataset.nimber ^ totalNimber;\n      if (objective < tower.dataset.nimber) {\n        var oldHeight = +tower.textContent;\n        var newHeight = oldHeight;\n        var nim = 0;\n        for (var j=2; j<=newHeight && nim<objective; ++j) {\n          while(newHeight % j == 0 && nim<objective) {\n            ++nim;\n            newHeight /= j;\n          }\n        }\n        newHeight = oldHeight / newHeight;\n        if (nimber(newHeight) != objective) throw Error(\'Fatal error\');\n        change(tower, newHeight, oldHeight, "PC reduces");\n        break;\n      }\n    }\n    prePlayerMove();\n  }\n}\nvar n, m;\nwhile(!Number.isInteger(n) || n < 0) n = +prompt("Number of towers");\nwhile(!Number.isInteger(m) || m < 0) m = +prompt("Height of each tower");\nvar totalNimber = 0;\nvar towers = document.getElementById(\'towers\');\nvar log = document.getElementById(\'log\');\nfor (var i=0; i<n; ++i) {\n  var nim = nimber(m);\n  totalNimber ^= nim;\n  var tower = document.createElement(\'div\');\n  tower.dataset.index = i+1;\n  tower.dataset.nimber = nim;\n  tower.textContent = m;\n  tower.addEventListener(\'click\', playerMove);\n  towers.appendChild(tower);\n}\npcMove();

\r\n

#towers > div {\n  display: inline-block;\n  border: 1px solid;\n  cursor: pointer;\n  margin: 5px;\n  padding: 5px;\n}

\r\n

<div id="towers"></div>\n<pre id="log"></pre>

\r\n

\r\n

\r\n

\n