## Friday, May 29, 2015

### Puzzling Matrices

A coworker of mine brought a puzzle into the staff lounge/dining area at work a few weeks ago. Since then a couple of us have worked on it on and off, and so far we've got...

…the frame, and a smattering of connected fragments. It's decidedly not an easy puzzle.

 Yes, that's the picture on the puzzle.
Progress on this puzzle, since we completed the outside frame, is typically in the range of 0–2 connections made per person, per day. It's a thousand-piece puzzle, fifty pieces wide by twenty tall. Yesterday as I managed to get a connection more by chance than skill, I wondered just how many connections there were in the puzzle.

It's not a very difficult problem, once we realize that the puzzle pieces are arranged in an essentially regular rectangular grid. This allows us to simplify the problem immensely (in true physicist fashion) by imagining the puzzle as a matrix of $$m=50$$ and $$n=20$$. The problem thus becomes a question of how many “edges” there are between all the pieces of a regular matrix.

We can start to break the problem down by looking at special cases: first of all, there are four corner pieces, each of which have only two connections. Then, there are a number of edge pieces, each of which will have three connections. Finally, the remainder of the pieces are interior pieces which have four connections each.

If we call the length and height of the puzzle m and n, then the number of edge pieces is going to be $$2\cdot[(m-2)+(n-2)]$$. (The picture below may help you picture the various areas involved; the edge pieces are the areas in green, the corners are blue.)

The number of interior pieces is simpler, it's simply $$(m-2)\cdot(n-2)$$. Now that we have the number of each type of piece, it's a simple matter to multiply them by the number of connections they have and divide by two since every connection is getting counted twice. This gives us a formula for a function:
\begin{align}f(m,n)&=\frac{1}{2}\Bigl[2\cdot4+3\cdot2\cdot\bigl[(m-2)+(n-2)\bigr]+4\cdot\bigl[(m-2)\cdot(n-2)\bigr]\Bigr]\\
&=\frac{1}{2}\Bigl[8+3(2m+2n-8)+4(mn-2m-2n+4)\Bigr]\\
&=\frac{1}{2}\bigl[8+6m+6n-24+4mn-8m-8n+16\bigr]\\
&=\frac{1}{2}[4mn-2m-2n]\\
&=2mn-(m+n)\end{align}
Phew! That's a lot friendlier looking. Funny, I remember when I used to hate algebra with a passion, but that was kinda fun. Absence really does make the heart grow fonder, I guess.

Anyway, we've got our function, but we should probably test it with easy cases. Let's take the cases where $$m=n=2$$ and $$m=n=3$$:

Here we have some (extremely simple) puzzles. For the first one, on the left, it's easy to see that there are four connections between the four pieces. Plugging 2 in for m and n in our function gives: $f(2,2)=2\cdot2\cdot2-(2+2)=8-4=4$ So that works. The second puzzle is larger, but it's still easy to count twelve connections between the nine pieces. Plugging 3 in for m and n gives us: $f(3,3)=2\cdot3\cdot3-(3+3)=18-6=12$ So it appears to hold water. Going back to the puzzle at work, which had $$m=50$$ and $$n=20$$, we have: $f(50,20)=2\cdot50\cdot20-(50+20)=2000-70=1930$Which is a lot of connections! Anyway, my curiosity is sated, and you now have a simple formula to use for party tricks or whatever in the future. A hui hou!