Project Euler Problem 434

Solution

Answer: 863253606

The key insight is that this is not really a rigidity problem — it becomes a graph connectivity counting problem.

Adding a diagonal to a grid cell “locks” the corresponding row and column together. This induces a bipartite graph:

one partition = the $m$ row directions,
the other partition = the $n$ column directions,
an edge = a diagonal added to a cell.

A theorem from grid rigidity says:

An $m\times n$ braced grid is rigid iff its associated bipartite graph is connected.

Thus:

$$R(m,n)$$

is exactly the number of connected labelled bipartite graphs with parts of sizes $m$ and $n$.

Let $B(m,n)$ denote this count. Since every possible edge between the two parts may be present or absent independently, there are

$$2^{mn}$$

total bipartite graphs.

To count connected ones, use inclusion–exclusion by isolating the connected component containing a fixed row vertex:

$$B(m,n) = 2^{mn} - \sum_{\substack{1\le a\le m\0\le b\le n\(a,b)\neq(m,n)}} \binom{m-1}{a-1} \binom{n}{b} B(a,b) 2^{(m-a)(n-b)}$$

Explanation:

choose $a-1$ additional row vertices to join the distinguished row,
choose $b$ column vertices,
require those selected vertices to form a connected component:

$B(a,b)$,

the remaining vertices can have arbitrary edges among themselves:

$2^{(m-a)(n-b)}$,

no edges may cross between the component and the outside.

We compute this DP for all $1\le m,n\le100$, then sum

$$S(100)=\sum_{i=1}^{100}\sum_{j=1}^{100}R(i,j) \pmod{1000000033}.$$

A clean Python implementation is:

from math import comb

MOD = 1000000033
N = 100

# R[m][n] = number of rigid m x n grids
R = [[0] * (N + 1) for _ in range(N + 1)]

# Precompute powers of 2^(mn)
pow2 = [[pow(2, i * j, MOD) for j in range(N + 1)]
        for i in range(N + 1)]

for m in range(1, N + 1):
    # boundary case needed by recurrence
    R[m][0] = 1 if m == 1 else 0

    for n in range(1, N + 1):
        total = pow2[m][n]

        # subtract disconnected graphs
        for a in range(1, m + 1):
            for b in range(n + 1):

                # skip the full graph itself
                if a == m and b == n:
                    break

                ways_choose = (
                    comb(m - 1, a - 1)
                    * comb(n, b)
                )

                contribution = (
                    ways_choose
                    * R[a][b]
                    * pow2[m - a][n - b]
                )

                total -= contribution

        R[m][n] = total % MOD

# Compute S(100)
answer = 0
for i in range(1, N + 1):
    for j in range(1, N + 1):
        answer += R[i][j]

answer %= MOD
print(answer)

Verification against the problem statement:

$R(2,3)=19$ ✓
$R(5,5)=23679901$ ✓
$S(5)=25021721$ ✓

Running the DP to $100\times100$ gives:

Answer: 863253606