Rigid Graphs

Recall that a graph is a collection of vertices and edges connecting the vertices, and that two vertices connected by an edge are called adjacent.
Graphs can be embedded in Euclidean space by associating each vertex with a point in the Euclidean space.
A flexible graph is an embedding of a graph where it is possible to move one or more vertices continuously so that the distance between at least two nonadjacent vertices is altered while the distances between each pair of adjacent vertices is kept constant.
A rigid graph is an embedding of a graph which is not flexible.
Informally, a graph is rigid if by replacing the vertices with fully rotating hinges and the edges with rods that are unbending and inelastic, no parts of the graph can be moved independently from the rest of the graph.

The grid graphs embedded in the Euclidean plane are not rigid, as the following animation demonstrates:

However, one can make them rigid by adding diagonal edges to the cells. For example, for the $2\times 3$ grid graph, there are $19$ ways to make the graph rigid:

Note that for the purposes of this problem, we do not consider changing the orientation of a diagonal edge or adding both diagonal edges to a cell as a different way of making a grid graph rigid.

Let $R(m,n)$ be the number of ways to make the $m \times n$ grid graph rigid.
E.g. $R(2,3) = 19$ and $R(5,5) = 23679901$.

Define $S(N)$ as $\sum R(i,j)$ for $1 \leq i, j \leq N$.
E.g. $S(5) = 25021721$.
Find $S(100)$, give your answer modulo $1000000033$.

This is a problem from the Project Euler, specifically problem 434. The purpose of Project Euler is to create, maintain and provide a platform for the encouragement of mathematical problem solving.

The question itself doesn’t directly relate to standard curriculum content taught in schools such as algebra or calculus. It’s more related to advanced topics in Graph Theory and Combinatorics. Generally, solutions to Project Euler problems involve a combination of mathematical insight, algorithm design and programming skills.

The problem is challenging. Below, I have provided an approach to solve it, and additional coding skills would be necessary for the actual calculation.

Let’s consider the orientation of each diagonal edge in a rigid grid graph as a binary state (either the diagonal edge is present, or it’s not). Then, for a n-by-m grid, since there are n*m cells, and each cell has two possibilities, there would be 2^(n*m) possibilities to check. For a 100-by-100 grid, there would be 2^10000, which is around 10^3000 possibilities, an unimaginably big number, even for a computer.

However, by observing that the rigidity of a grid depends only on its adjacent cells, one can optimise this by using dynamic programming. To do this, we note that the states of the cells in row i depends only on the states of the cells in row i-1, and row i-2.

Therefore, if we consider the states of cells in two consecutive rows together, there would only be 2^(2m) possible states (~10000 for m = 100), a much smaller number.

With this dynamic programming table, the problem can be solved with reasonable time complexity, and is basically a programming task after the table has been created.

However, computing the actual value of S(100) modulo 1000000033 would still be quite challenging and would likely require writing a computer program. If you need detailed code to obtain the exact result, I would suggest reaching out to a forum that specializes in coding or Project Euler problem-solving, as this is a highly specific and advanced mathematical problem.

More Answers: