Tower Breakers - nim game variation with divisors

Question

I have encountered a game called Tower Breakers, which seems a variation of the nim game.

• There are two players, player 1 and player 2.
• Initially there are n towers, where each tower is of height m, both n and m positive integers.
• Player 1 begins, and then they move in alternating turns.
• In each turn, a player can choose a tower of height x > 1 and reduce its height to a positive integer y, where 1 <= y < x and y evenly divides x.
• If the current player is unable to make any move, loses the game.

Is there some winning strategy? What if the towers don't have equal heights at the beginning?

Preachment

I'm reposting this as a self-answered question because the original one was removed by a bot. I don't want my answer to be lost. – Preachment

I'm voting to close this question as off-topic because it is not about programming. – Phonon

@Phonon Well, it's about algorithms, which are explicitly on topic – Preachment

Answer 1

General case

This can indeed be solved like a nim game, but using a different nimber definition.

In the original game, the nimber of a tower is simply defined as its height.

In this variation, the nimber of a tower T of height h(T) = x = p₁ˢ¹ … pₖˢᵏ, with pᵢ prime, is

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

The nimber of the list of n towers L = (T₁, …, Tₙ) is the usual

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

If the nimber is 0 when your turn begins, you will lose whatever you do, assuming the other player plays perfectly.

Otherwise, you only need to do a move which makes the nimber become zero.

You can do this because if n(L) > 0 then there is a tower, let's assume without loss of generalization it's Tₙ, such that n(Tₙ) ⊕ n(L) < n(L).

Such a tower exists: the leftmost bit of n(L) is 1 and that's because some tower Tₙ has a 1 in that bit position. Doing n(Tₙ) ⊕ n(L) you kill that 1 and don't alter the more significant bits of n(Tₙ) because it's the leftmost bit of n(L). So n(Tₙ) ⊕ n(L) is smaller.

Then you only need to modify Tₙ to Tₙ' such that n(Tₙ') = n(Tₙ) ⊕ n(L), and thus

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

This move is always possible, for example reducing the height to x' = p₁ˢ¹ … pₗ₋₁ˢˡ⁻¹ pₗᵈ, with l <= k and 0 < d <= sₗ, such that s₁ + … + sₗ₋₁ + d = n(Tₙ) ⊕ n(L). x' divides x by construction, and x' < x so they are different.

Once the nimber is zero, whatever the movement the other player does, it will affect the nimber of that tower, and then the total xor n(L) will no longer be zero. You then repeat the same strategy.

Particular case

In the particular case where all towers have the same height,

• If there is an even number of towers or towers that have a height 1, the total nimber will be zero, and thus player 2 will win if plays optimally.
• Otherwise, the total nimber will be non-zero, and thus player 1 will win if plays optimally.

This can in fact be shown without using nimbers:

• If there is an even number of towers, player 2 can group them in pairs. The invariant he wants to maintain is that both towers in each pair have the same height. Whenever player 1 makes a move, this invariant will break. Then player 2 only needs to do the same move to the other tower in the pair (it will be a valid move, otherwise player 1 couldn't have done it). Eventually, all towers will reach height 1, and player 2 will win.

• If there is an odd number of towers (with height > 1), player 1 can reduce the height of the last tower to 1. In practice, this is like eliminating that tower. So now it will be player 2's turn, but the number of playable towers will be even. So the previous case applies, and player 1 will win.

Play

You can play in the following snippet:

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>

Preachment

Answer 2

Here's the answer for Tower Breakers (equal height).

Answer

• If M is 1, the second player will win.
• if N is even (N % 2 == 0) and M is not 1, the second player will win.
• If N is odd (N % 2 == 1) and M is not 1, the first player will win.

Here is my C++ code. (It got Accepted)

#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;
    }
}

Why it is correct?

• If M is 1, it is obvious that Second player will win because the First player can't move.
• If N is even, Second player can do same operation for first players. For example, if First player move {4, 4, 4, 4} -> {2, 4, 4, 4}, Second player can move {2, 4, 4, 4} -> {2, 2, 4, 4}. Finally Second player can make {1, 1, 1, ..., 1}, so Second player can win.
• If N is odd, First player can reduce height of first tower to 1, so you can return to "N is even" case. So, you can prove that first player wins.
• So, the answer is correct.

Harriott

Even though the code may have been accepted, the proof seems to be incomplete. "If N is even, Second player can do same operation for first players" - Why is that the optimal strategy for player 2? "If N is odd, First player can reduce height of first tower to 1" - Why is that the optimal strategy for player 1? – Brougham

Answer 3

1. If M is 1, both players can't make a move, so the 2nd player will win.
2. If N is even (N % 2 == 0) and M is not 1, the 2nd player's strategy is copying 1st player's move, so the 2nd player will win when all tower height is 1.
3. If N is odd (N % 2 == 1) and M is not 1:

• The 1st player reduce a tower height to 1. Now number of tower is (N-1), the 2nd player become the 1st player and vice versa.
• According case 2, the winner is the 1st player.

Johathan

Answer 4

All tests on HackerRank pass with this solution:

if(n%2 == 0 || m==1) return 2;  // if number of towers even or m==1, player 2 wins
return 1;                       // else player 1 wins

Basically this is @hideaki's answers as code.

Gadgeteer