Nim on Towers of Hanoi

This problem combines the game of Nim with the Towers of Hanoi. For a brief introduction to the rules of these games, please refer to Problem 301 and Problem 497, respectively.
The unique shortest solution to the Towers of Hanoi problem with $n$ disks and $3$ pegs requires $2^n-1$ moves. Number the positions in the solution from index 0 (starting position, all disks on the first peg) to index $2^n-1$ (final position, all disks on the third peg).
Each of these $2^n$ positions can be considered as the starting configuration for a game of Nim, in which two players take turns to select a peg and remove any positive number of disks from it. The winner is the player who removes the last disk.
We define $f(n)$ to be the sum of the indices of those positions for which, when considered as a Nim game, the first player will lose (assuming an optimal strategy from both players).
For $n=4$, the indices of losing positions in the shortest solution are 3,6,9 and 12. So we have $f(4) = 30$.
You are given that $f(10) = 67518$.
Find $f(10^5)$. Give your answer modulo $1\,000\,000\,007$.

While this problem is presented in the context of two games, it’s truly an exercise in understanding the properties of Nim and binary representation operations.

To start, let’s break it down:

1. In the “Towers of Hanoi” problem, each move represents a state change from one binary number to another in an ordered list of binary numbers.
2. Each peg in the game corresponds to a bit position in the binary representation of the state.
3. Each penny stacked on a given peg corresponds to a 1 bit in that position in the binary representation.

Let’s assume the binary state 101 to be a losing state.

For a move to be made to this state, it must have occurred from a previous state. Let’s call this previous state X. One possible way to reach state 101 could be changing state 111 (i.e., making a move on the rightmost peg).

However, this would be a winning state because a move could be made to 101 (a losing state). Therefore, any state from which we could make a move to a losing state is a winning state.

This provides the hint on how to proceed: a losing state in the Nim game is one where all binary digits (from right to left) must have Blocks of 1s with an even count. The binary form of each number from 1 to $2^{n} – 1$ is calculated and all the counts are checked.

A “block of 1s” is defined as a contiguous sequence of ones bounded by a zero on either side in the binary form of a number. We will define a number as a losing number if, in its binary representation, each block of 1s has an even length.

As an example, let’s consider the binary number 11010011011:

– The first “block” of 1s at the right end of the number has length 2, which is even.
– The next “block” of 1s has length 3, which is odd.
– The final “block” of 1s has length 2, which is even.

Therefore, the number 11010011011 would be a losing state in the Nim game.

So now we can write a function, which directly calculates the losing indices which are in the sequence of Tower of Hanoi’s states. We can represent this function in Python:

“`python
MOD = 1000000007

def f(n):
a, b, p, ans = 1, 1, 1, 0
for i in range(n << 1): a = a * 3 % MOD if i & 1: b = b * 3 % MOD else: p = p * 2 % MOD ans = (ans + a - b + MOD) % MOD return ans * p % MOD print(f(10**5)) ``` In the above script, we iterate over a range twice the size of n. For each iteration, we multiply a and b by 3 (mod MOD). In every even iteration, we multiply p by 2 and adjust the answer by adding a and subtracting b (mod MOD). At the end, we multiply our resultant answer with p and apply mod MOD, before we return and print it.

More Answers: