I have encountered a game called Tower Breakers, which seems a variation of the nim game.
n towers, where each tower is of height m, both n and m positive integers.x > 1 and reduce its height to a positive integer y, where 1 <= y < x and y evenly divides x.Is there some winning strategy? What if the towers don't have equal heights at the beginning?
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.
In the particular case where all towers have the same height,
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.
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>