Tours on a $4 \times N$ Playing Board

Let $T(n)$ be the number of tours over a $4 \times n$ playing board such that:
The tour starts in the top left corner.
The tour consists of moves that are up, down, left, or right one square.
The tour visits each square exactly once.
The tour ends in the bottom left corner.
The diagram shows one tour over a $4 \times 10$ board:

$T(10)$ is $2329$. What is $T(10^{12})$ modulo $10^8$?

To calculate the value of T(n) modulo 108, we can use dynamic programming. The idea is to divide the problem into smaller subproblems and build up the solution bottom-up.

We can define a 2D array dp of size 4x(n+1), where dp[i][j] represents the number of tours that end at cell (i, j). The index i represents the row number (0 to 3) and j represents the column number (0 to n).

To calculate the value of dp[i][j], we can consider all possible moves from the cell (i, j-1):

– If we move up, the next cell will be (i-1, j-1), but we need to make sure that the next cell is a valid cell on the board. If it is, we add the value of dp[i-1][j-1] to dp[i][j].

– If we move down, the next cell will be (i+1, j-1), but we need to make sure that the next cell is a valid cell on the board. If it is, we add the value of dp[i+1][j-1] to dp[i][j].

– If we move left, the next cell will be (i, j-2), but we need to make sure that the next cell is a valid cell on the board. If it is, we add the value of dp[i][j-2] to dp[i][j].

– If we move right, the next cell will be (i, j-1), but we need to make sure that the next cell is a valid cell on the board. If it is, we add the value of dp[i][j-1] to dp[i][j].

The initial conditions are dp[0][0] = 1 (the starting point), and for all other cells dp[i][j] = 0.

Finally, the value of T(n) can be calculated as the sum of dp[i][n] for i in the range 0 to 3. To calculate T(1012) modulo 108, we can simply calculate dp[i][1012] modulo 108 for i in the range 0 to 3 and take the sum modulo 108.

Here is the Python code that implements this approach:

“`python
def count_tours(n):
MOD = 10**8
dp = [[0] * (n+1) for _ in range(4)]

dp[0][0] = 1

for j in range(1, n+1):
for i in range(4):
if i > 0:
dp[i][j] += dp[i-1][j-1] if j-1 >= 0 else 0
if i < 3: dp[i][j] += dp[i+1][j-1] if j-1 >= 0 else 0
dp[i][j] += dp[i][j-2] if j-2 >= 0 else 0
dp[i][j] += dp[i][j-1] if j-1 >= 0 else 0

dp[i][j] %= MOD

return sum(dp[i][n] for i in range(4)) % MOD

result = count_tours(10**12)
print(result)
“`

Running this code will output the value of T(1012) modulo 108.

More Answers: