8
$\begingroup$

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.

enter image description here

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:

enter image description here

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.

$\endgroup$
1
  • $\begingroup$ That second image showing the flexibility of the grid hurts my brain because it keeps trying to make it look 3D... $\endgroup$ – Dave Jun 2 '15 at 13:56
3
$\begingroup$

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}$).

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ A bit more direct way to prove stiffness: put diagonals braces across the first row and column. They are now made of triangles, so are stiff. Each other vertex is helped in place by the edges to the two vertices above it and to its left and so can't move. $\endgroup$ – xnor Jun 1 '15 at 3:17
  • $\begingroup$ @xnor But just giving an example doesn't prove that that example is minimal... even if your configuration is such that removing any brace makes it non-stiff, that doesn't show that a configuration with fewer braces doesn't exist. $\endgroup$ – 2012rcampion Jun 1 '15 at 3:19
  • $\begingroup$ @xnor You can actually extend your example to any row and column, and it works the same way. I actually worked with a real-world situation like this where we constructed a rigid cross-shaped structure, and then filled in the four quadrants with (individually) unconstrained members; together the whole grid was stiff. $\endgroup$ – 2012rcampion Jun 1 '15 at 3:21
  • $\begingroup$ @2012rcampion I have to agree with xnor, you prove that, in order to limit the degrees of freedom, you need AT LEAST 2n-1. Your proof lacks however what xnor states, that there is actually a solution that works for the theoretical minimum. Furthermore, I think xnor is right to state they need to be on the outer edges for a minmal solution. If not the case, stuff like the option displayed in the question is still possible (assuming 'rigid' only applies to guaranteeing a square remaining square, and doesn't affect 'flexing' along the outer edge of said square) $\endgroup$ – Tim Couwelier Jun 1 '15 at 6:41
  • $\begingroup$ @TimCouwelier I challenge you to show me a counterexample of a nonrigid grid that satisfies the criteria in my proof. $\endgroup$ – 2012rcampion Jun 1 '15 at 11:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.