Tower Breakers - вариация игры с делителями

Я столкнулся с игрой под названием Tower Breakers, которая кажется разновидностью игры NIM.

  • Есть два игрока, игрок 1 и игрок 2.
  • Изначально есть n башни, где каждая башня имеет высоту m, и то и другое n а также m целые положительные числа.
  • Игрок 1 начинает, а затем они ходят по очереди.
  • В каждом ходу игрок может выбрать башню высоты x > 1 и уменьшить его высоту до положительного целого числа y, где 1 <= y < x а также y равномерно делит x,
  • Если текущий игрок не может сделать ход, проигрывает игру.

Есть ли какая-нибудь выигрышная стратегия? Что если башни не имеют одинаковой высоты в начале?

Источник

3 ответа

Решение

Общий случай

Это действительно может быть решено как игра nim, но с использованием другого определения nimber.

В оригинальной игре количество башни просто определяется как ее высота.

В этом варианте нимбер башни T высоты h(T) = x = p₁ˢ¹ … pₖˢᵏ, с pᵢ премьер, это

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

Нимбер из списка n башни L = (T₁, …, Tₙ) это обычный

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

Если nimber равен 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 поэтому они разные.

Как только nimber равен нулю, независимо от того, какое движение выполняет другой игрок, это повлияет на nimber этой башни, а затем на общее xor n(L) больше не будет ноль. Затем вы повторяете ту же стратегию.

Частный случай

В частном случае, когда все башни имеют одинаковую высоту,

  • Если существует четное количество башен или башен высотой 1, общее число нимеров будет равно нулю, и, таким образом, игрок 2 выиграет, если сыграет оптимально.
  • В противном случае общее число будет ненулевым, и, таким образом, игрок 1 выиграет, если сыграет оптимально.

На самом деле это можно показать без использования чеков:

  • Если количество башен четное, игрок 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>

Источник

Вот ответ для Башенных Разрушителей (равной высоты).

Ответ

  • Если М равен 1, второй игрок выиграет.
  • если N четное (N % 2 == 0) и М не равно 1, второй игрок выиграет.
  • Если N нечетно (N % 2 == 1) и М не 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;
    }
}

Почему это правильно?

  • Если М равен 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 является четным". Таким образом, вы можете доказать, что выигрывает первый игрок.
  • Итак, ответ правильный.
Источник
  1. Если 1, оба игрока не могут сделать ход, поэтому второй игрок выиграет.
  2. Если даже ( N % 2 == 0), а не 1, стратегия 2-го игрока копирует ход 1-го игрока, поэтому 2-й игрок выиграет, когда высота всех башен равна 1.
  3. Если N нечетный ( N % 2 == 1) а также M не 1:
  • Первый игрок уменьшает высоту башни до 1. Теперь количество башен ( N-1), 2-й игрок становится 1-м и наоборот.
  • В случае 2 победителем становится 1-й игрок.
Источник
Другие вопросы по тегам