Colouring a Strip

A certain type of tile comes in three different sizes – $1 \times 1$, $1 \times 2$, and $1 \times 3$ – and in four different colours: blue, green, red and yellow. There is an unlimited number of tiles available in each combination of size and colour.
These are used to tile a $2\times n$ rectangle, where $n$ is a positive integer, subject to the following conditions:

The rectangle must be fully covered by non-overlapping tiles.
It is not permitted for four tiles to have their corners meeting at a single point.
Adjacent tiles must be of different colours.

For example, the following is an acceptable tiling of a $2\times 12$ rectangle:

but the following is not an acceptable tiling, because it violates the “no four corners meeting at a point” rule:

Let $F(n)$ be the number of ways the $2\times n$ rectangle can be tiled subject to these rules. Where reflecting horizontally or vertically would give a different tiling, these tilings are to be counted separately.
For example, $F(2) = 120$, $F(5) = 45876$, and $F(100)\equiv 53275818 \pmod{1\,000\,004\,321}$.
Find $F(10^{16}) \bmod 1\,000\,004\,321$.

This type of problem making use of combinatorics, modular arithmetic and dynamic programming, is quite complex and generally belongs to areas of mathematics that are higher level than high school mathematics (e.g. college-level mathematic study or Olympiad-level maths competitions). Given the complexity of the problem, it also requires significant computational power to solve it directly for large values of n like $10^{16}$.

To conceptually approach this problem, the idea is to assign states based on how the last two columns of the tiling have been filled (0=blue, 1=green, 2=red, 3=yellow). The total number of possible states is $4^4=256$ since there are 4 colors to choose and 4 blocks in the last two columns.

Enumerate all possible next states for each current state and calculate the matrices of transition probabilities between states. The aim is to iterate over the transition matrix and attempt to find a cycle, which has a period T.

To save computational time, one can perform a matrix fast power operation to compute the $n$-th power of the transition matrix. Since the calculation of the high-dimensional power of the matrix involves a large number of multiplication operations, there is a need to take modulus on both the matrix elements and the exponents during the operation to keep the result within the limit of computation.

F[100] can be computed more easily and directly utilizing the above idea, but calculating F[$10^{16}$] requires also calculating the cycle period of the matrix, which can be used to reduce the exponent by modulo T. By discovering the cyclic structure in the transition matrix, and utilizing the fact that matrix multiplication is associative, one can perform this computation much more efficiently than directly calculating the $10^{16}$-th power of the transition matrix.

This is the general idea of the solution, but there are a lot of specifics and details including programming the computation that are not outlined. This problem requires a solid background in combinatorics, dynamic programming and modular arithmetic as well as programming skills.

More Answers: