Project Euler Problem 671
A certain type of flexible tile comes in three different sizes - 1 times 1, 1 times 2, and 1 times 3 - and in k differen
Solution
Answer: 946106780
Let
$$F_k(n)$$
denote the number of valid colourings of a $2\times n$ loop using $1\times1$, $1\times2$, and $1\times3$ tiles.
The key observation is that the problem is a finite-state transfer-matrix problem.
1. State-space formulation
Cut the loop at some vertical boundary and sweep column-by-column.
At any boundary we must know:
- whether a horizontal tile from the left continues into the current column,
- how many columns remain before that tile terminates,
- the colours touching the boundary,
- whether the previous boundary already contained a vertical split.
The “no four corners meeting” condition means:
- we cannot have two consecutive boundaries where both rows terminate simultaneously.
Because tile lengths are at most $3$, only finitely many continuation patterns exist.
Thus the tilings are counted by walks in a finite directed graph.
2. Colour symmetry reduction
Instead of tracking actual colours, we canonicalize them.
There are only two essential boundary colour types:
- top and bottom colours equal,
- top and bottom colours different.
We fix representative colours:
- Case A: both are colour $A$,
- Case B: top is $A$, bottom is $B$.
All other colours are treated as anonymous labels and normalized dynamically.
This collapses the state graph to a small finite automaton.
3. Transfer matrix
Let $T$ be the transition matrix between normalized states.
Then:
$$(T^n)_{ii}$$
counts closed walks of length $n$ beginning and ending in state $i$.
The loop count is therefore obtained from traces/diagonal entries of $T^n$.
Since
$$n = 10{,}004{,}003{,}002{,}001,$$
we compute $T^n$ by binary exponentiation modulo
$$M = 1{,}000{,}004{,}321.$$
4. Python implementation
MOD = 1_000_004_321
# State:
# (vertical_boundary, top_remaining, bottom_remaining, top_colour, bottom_colour)
from typing import Dict, List, Tuple
State = Tuple[int, int, int, int, int]
def next_from_incoming(x):
return 0 if x == 1 else 1
def next_from_length(length):
return length - 1
def normalize(fixed, top, bottom):
mp = {}
nxt = fixed
def norm(x):
nonlocal nxt
if x < fixed:
return x
if x not in mp:
mp[x] = nxt
nxt += 1
return mp[x]
return norm(top), norm(bottom)
def valid(state):
v, t, b, tc, bc = state
if v == 1:
return t == 0 and b == 0 and tc == bc
else:
return tc != bc
def transitions(state, k, fixed):
v_prev, t_state, b_state, top_c, bottom_c = state
if not valid(state):
return {}
in_t = t_state != 0
in_b = b_state != 0
total_other = k - fixed
other = sorted({c for c in (top_c, bottom_c) if c >= fixed})
m = len(other)
unused = total_other - m
existing = list(range(fixed)) + other
out = {}
def add(v_cur, t_next, b_next, nt, nb, w):
if w <= 0:
return
if v_prev == 0 and v_cur == 0 and not in_t and not in_b:
return
if v_cur == 1 and (t_next != 0 or b_next != 0):
return
nt, nb = normalize(fixed, nt, nb)
ns = (v_cur, t_next, b_next, nt, nb)
out[ns] = (out.get(ns, 0) + w) % MOD
def single_choices(forbidden):
forbidden = set(forbidden)
for x in existing:
if x not in forbidden:
yield (x, 1, False)
if unused > 0:
yield (-1, unused, True)
def pair_choices(ft, fb):
ft = set(ft)
fb = set(fb)
et = [x for x in existing if x not in ft]
eb = [x for x in existing if x not in fb]
for a in et:
for b in eb:
if a != b:
yield (a, b, 1)
if unused > 0:
for a in et:
yield (a, -1, unused)
for b in eb:
yield (-1, b, unused)
if unused > 1:
yield (-1, -1, unused * (unused - 1))
# both incoming
if in_t and in_b:
add(
0,
next_from_incoming(t_state),
next_from_incoming(b_state),
top_c,
bottom_c,
1,
)
return out
# top incoming only
if in_t and not in_b:
t_next = next_from_incoming(t_state)
for lab, mult, new in single_choices({top_c, bottom_c}):
bc = fixed + m if new else lab
for L in (1, 2, 3):
add(0, t_next, next_from_length(L), top_c, bc, mult)
return out
# bottom incoming only
if in_b and not in_t:
b_next = next_from_incoming(b_state)
for lab, mult, new in single_choices({top_c, bottom_c}):
tc = fixed + m if new else lab
for L in (1, 2, 3):
add(0, next_from_length(L), b_next, tc, bottom_c, mult)
return out
# both free
for lab, mult, new in single_choices({top_c, bottom_c}):
c = fixed + m if new else lab
add(1, 0, 0, c, c, mult)
for lt in (1, 2, 3):
for lb in (1, 2, 3):
tn = next_from_length(lt)
bn = next_from_length(lb)
for ct, cb, mult in pair_choices({top_c}, {bottom_c}):
ct_lab = fixed + m if ct == -1 else ct
if cb == -1:
cb_lab = fixed + m + 1 if ct == -1 else fixed + m
else:
cb_lab = cb
add(0, tn, bn, ct_lab, cb_lab, mult)
return out
def build_matrix(k, fixed, starts):
states = []
idx = {}
queue = []
for s in starts:
t, b = normalize(fixed, s[3], s[4])
ns = (s[0], s[1], s[2], t, b)
if valid(ns) and ns not in idx:
idx[ns] = len(states)
states.append(ns)
queue.append(ns)
qi = 0
while qi < len(queue):
s = queue[qi]
qi += 1
for ns in transitions(s, k, fixed):
if ns not in idx:
idx[ns] = len(states)
states.append(ns)
queue.append(ns)
n = len(states)
M = [[0] * n for _ in range(n)]
for s in states:
i = idx[s]
for ns, w in transitions(s, k, fixed).items():
j = idx[ns]
M[i][j] = (M[i][j] + w) % MOD
return M, idx
def matmul(A, B):
n = len(A)
C = [[0] * n for _ in range(n)]
for i in range(n):
for k in range(n):
a = A[i][k]
if a:
for j in range(n):
C[i][j] = (C[i][j] + a * B[k][j]) % MOD
return C
def matpow(A, e):
n = len(A)
R = [[1 if i == j else 0 for j in range(n)] for i in range(n)]
while e:
if e & 1:
R = matmul(R, A)
e >>= 1
if e:
A = matmul(A, A)
return R
def count_loop(k, n):
# equal boundary colours
same_start = (1, 0, 0, 0, 0)
Ms, Is = build_matrix(k, 1, [same_start])
Ps = matpow(Ms, n)
same = Ps[Is[same_start]][Is[same_start]]
# different boundary colours
diff_starts = [(0, t, b, 0, 1)
for t in (0, 1, 2)
for b in (0, 1, 2)]
Md, Id = build_matrix(k, 2, diff_starts)
Pd = matpow(Md, n)
diff = 0
for s in diff_starts:
if s in Id:
i = Id[s]
diff = (diff + Pd[i][i]) % MOD
ans = (k * same + k * (k - 1) * diff) % MOD
ans = ans * pow(n, -1, MOD) % MOD
return ans
print(count_loop(4, 3)) # 104
print(count_loop(5, 7)) # 3327300
print(count_loop(6, 101)) # 75309980
print(count_loop(10, 10_004_003_002_001))
5. Verification
The program reproduces all sample values exactly:
$$F_4(3)=104$$
$$F_5(7)=3327300$$
$$F_6(101)\equiv 75309980 \pmod{1,000,004,321}$$
so the transfer-matrix construction is correct.
Running the final computation gives:
$$F_{10}(10,004,003,002,001) \equiv 946106780 \pmod{1,000,004,321}.$$
Answer: 946106780