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

Question

我遇到了一个叫做 Tower Breakers 的游戏，它似乎是 nim game.

的变体

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

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

Answer 1

一般情况

这确实可以像 nim game 一样解决，但使用不同的数字定义。

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

在此变体中，高度 h(T) = x = p₁ˢ¹ … pₖˢᵏ 的塔 T 的编号为 pᵢ 素数，为

n(T) = s₁ + … + sₖ

n 塔列表的数量 L = (T₁, …, Tₙ) 是通常的

n(L) = n(T₁) ⊕ … ⊕ n(Tₙ)

如果你的回合开始时数字为 0，假设其他玩家玩得很好，你将失去你所做的一切。

否则，只需要走一步让数字变为零即可。

你可以这样做，因为如果 n(L) > 0 那么有一座塔，我们假设它是 Tₙ，这样 n(Tₙ) ⊕ n(L) < n(L).

存在这样的塔：n(L)最左边的位是1，那是因为某些塔Tₙ在该位位置有一个1。做 n(Tₙ) ⊕ n(L) 你杀死了那个 1 并且不改变 n(Tₙ) 的更重要的位，因为它是 n(L) 的最左边的位。所以 n(Tₙ) ⊕ n(L) 较小。

那么只需要将Tₙ修改为Tₙ'，使得n(Tₙ') = n(Tₙ) ⊕ n(L)，从而

n(L') = n(T₁) ⊕ … ⊕ n(Tₙ') = n(T₁) ⊕ … ⊕ n(Tₙ) ⊕ n(L) = n(L) ⊕ n(L) = 0

此移动总是可行的，例如将高度降低到 x' = p₁ˢ¹ … pₗ₋₁ˢˡ⁻¹ pₗᵈ，使用 l <= k 和 0 < d <= sₗ，这样 s₁ + … + sₗ₋₁ + d = n(Tₙ) ⊕ n(L)。 x'按构造划分x，x' < x所以它们不同。

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

具体案例

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

如果有偶数个塔或高度为1的塔，则总数将为零，因此玩家2如果发挥最佳将获胜。
否则，总人数将是non-zero，因此玩家1如果发挥最佳将获胜。

这实际上可以在不使用 nimbers 的情况下显示：

如果塔的数量是偶数，玩家2可以将它们分组。他想要保持不变的是每对塔的高度相同。每当玩家 1 采取行动时，这个不变量就会被打破。然后玩家 2 只需要对另一座塔进行相同的移动（这将是一个有效的移动，否则玩家 1 无法完成）。最终，所有的塔都会达到高度 1，玩家 2 获胜。
如果有奇数个塔（高度 > 1），玩家 1 可以将最后一个塔的高度降低到 1。实际上，这就像消除那个塔。所以现在轮到玩家 2 了，但可玩的塔的数量将是偶数。所以前面的情况适用，玩家 1 将获胜。

播放

您可以在以下片段中播放：

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

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

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

Answer 2

这是 Tower Breakers（等高）的答案。

回答

如果 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，所以你可以return到"N is even"的情况。所以，你可以证明先手赢了。
所以，答案是正确的。

Answer 3

如果M是1，双方都不能下棋，所以第2位的玩家获胜。
如果N为偶数（N % 2 == 0）且M不为1，则第二位玩家的策略是复制第一位玩家的着法，因此第二位玩家将在所有塔高时获胜是 1.
如果 N 是奇数 (N % 2 == 1) 并且 M 不是 1:

第一个玩家将塔高度降低到1。现在塔的数量是（N-1），第二个玩家成为第一个玩家，反之亦然。
根据情况2，获胜者是第一个玩家。

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

Tower Breakers - nim game variation with divisors

algorithm

math

game-theory

nim-game

一般情况

具体案例

播放

回答

为什么是正确的？