Bracing a Flexible Grid

Question

Suppose that you build an $n$ by $n$ grid out of metal rods, joined at their ends in such a way that they can rotate about the joints. Below is the grid when $n=3$, along with an illustration of its flexibility.

This grid can be made rigid by "bracing" sufficiently many of the squares with a diagonal rod. You could brace all the squares, but there are more efficient ways. For example, the below structure is rigid:

What is the fewest number of squares you need to brace to make the grid rigid?

If the optimal number is $b$, a good answer should show how to brace the grid with $b$ braces, and convince the reader why any grid with only $b-1$ braced squares is flexible.

Source: Mathematical Mind Benders, Peter Winkler.

Answer 1

Partition the bars of the grid into $2n$ bundles of $n+1$ bars each in the most canonical way. Each of these bundles is necessarily parallel to begin with and stays parallel under any minor deformation of the grid. On the other hand, the orientations of these bundles are completely independent of each other, so for any tuple of $2n$ orientations, you could align the unreinforced grid so the $k$th bundle has the $k$th orientation.

Now bracing a single square constrains two of these bundles (the bundles which the square is made of) to be aligned orthogonally, nothing more and nothing less. Let's call two bundles directly constrained if there is a braced square with edges in these bundles. You can imagine this as a graph, where the $2n$ vertices are bundles and the edges are direct constraints.

Now consider the constrained components of this graph. For each constrained component, the orientation of a single bundle within completely determines the orientation of every other bundle in the same component. Yet the orientation of this component is still independent of the orientation of any bundle not in this component. This means that if we have more than one constrained component, our grid is not rigid.

Now let's count the constrained components. With zero braced squares, we have $2n$ components. Every braced square adds exactly one direct constraint, so adding a square reduces the number of codependent components by exactly one. So to make the entire structure rigid, we need to have exactly one constrained component, which means we need at least $2n-1$ braced squares.

This lower limit can be achieved by bracing $2n-1$ squares in an L shape along two edges, or a staircase shape along a diagonal, or a cross shape produced by any row and any column of squares in the grid, or actually any set of squares induced by any possible subtree of the graph of all possible direct constraints (which is a complete bipartite graph $K_{n,n}$).

Answer 2

An $n\times n$ grid has $(n+1)^2$ vertices, each with two degrees of freedom. Since we wish the overall grid to have only $3$ degrees of freedom ($2$ for translation and $1$ for rotation), we need

$$ 2(n+1)^2-3 $$

constraints. Each bar provides a one-dimensional constraint, and we start with $2n^2+2n$ bars (two for the bottom and left sides of each of the $n^2$ squares, and $n$ for each of the top and right sides), so the number of additional bars we need is:

$$ b = (2(n+1)^2-3)-(2n^2+2n) = 2n-1 $$

Update

Mike requests a constructive proof in the question, so here's an attempt:

When $n=1$, we can trivially stiffen the grid by stiffening the only square in the grid. Thus, $b(1)=1$.

Take an $n\times n$ grid that is already stiff, and add one row and column to make an $(n+1)\times(n+1)$ grid. The additional row and column can each bend independently of each other. If we stiffen the new corner, we can still bend (as seen in the OP's first diagram). Thus, in order to stiffen the new grid, we must stiffen one square in the new row and one in the new column, increasing $b$ by $2$. Therefore $b(n+1)=b(n)+2$, or equivalently $b(n)=2n-1$.

This proof by induction gives us a general method to construct any minimal stiffening of a grid.

It also leads to a set of rules to determine whether an arbitrary grid is stiff. A stiff grid must have a stiffened square in each row and each column, and every stiff square shares a column or row with another stiff square.