 |
| Percy Alexander MacMahon [1] |
We consider a collection of 24 squares, where the four edges (top, right, bottom, left) are colored by three different colors.
 |
| MacMahon Squares |
These 24 squares are all the squares we can make this way using three colors. Note that rotation does not give us a new square. The number of squares we can create using \(n\) colors is [3]: \[\frac{n(n+1)(n^2-n+2)}{4}\] This formula is not obvious to me.
These 24 squares need to be placed on a \(4 \times 6\) grid (allowing rotation), subject to the following constraints:
- The edges at the border of the grid should be white
- The touching edges of two neighboring squares should have the same color
The best is to show a feasible solution:
 |
| A single feasible solution |
My first task: try to develop a mathematical programming model that finds a single feasible solution. For this we use a bunch of sets:
- \(i \in \{1,\dots,4\}\) indicates the row in the grid,
- \(j \in \{1,\dots,6\}\) is the column,
- \(k \in \{1,\dots,24\}\) is the square,
- \(r \in \{0^{\circ},45^{\circ},90^{\circ},135^{\circ}\}\) is the rotation applied,
- \(c \in \{\color{darkgreen}{\mathit{White}},\color{darkgreen}{\mathit{Red}},\color{darkgreen}{\mathit{Blue}}\}\) are the colors,
- \(e \in \{\color{darkgreen}{\mathit{Top}},\color{darkgreen}{\mathit{Right}},\color{darkgreen}{\mathit{Bottom}},\color{darkgreen}{\mathit{Left}}\}\) is an edge,
- \(\color{darkblue}{\mathit{Sq}}_{k,r,e,c}\) is the color for an edge after rotation of square \(k\). This describes our collection of squares,
- \(\color{darkblue}{\mathit{Border}}_{i,j,e}\) identifies the edges that form the outer border of the grid,
- \(\color{darkblue}{\mathit{Touch}}_{i,j,e,i',j',e'}\) gives us the edges of neighboring cells in the grid that touch each other.
I introduce two variables: \[\color{darkred}x_{i,j,k,r} = \begin{cases} 1 & \text{if square $k$ is placed at $(i,j)$ after rotation}\\ 0 & \text{otherwise}\end{cases}\] and \[\color{darkred}y_{i,j,e,c} = \begin{cases} 1 & \text{if edge $e$ for the square at $(i,j)$ has color $c$}\\ 0 & \text{otherwise}\end{cases}\]
We have fairly standard assignment constraints: \[\begin{align} & \sum_{i,j,r} \color{darkred}x_{i,j,k,r} = 1 && \forall k \\ & \sum_{k,r} \color{darkred} x_{i,j,k,r} = 1 && \forall i,j \end{align}\] The variables \(\color{darkred}x\) and \(\color{darkred}y\) are linked as follows: \[\color{darkred}y_{i,j,e,c} = \sum_{k,r|\color{darkblue}{\mathit{Sq}}(k,r,e,c)} \color{darkred}x_{i,j,k,r} \>\> \forall i,j,e,c\] The constraint to fix the color of the edges at the border to White is: \[\color{darkred}y_{i,j,e,\color{darkgreen}{\mathit{White}}}= 1 \>\> \forall \color{darkblue}{\mathit{Border}}_{i,j,e}\] Finally the constraint to align colors where edges of neighboring squares touch each other: \[\color{darkred}y_{i,j,e,c} = \color{darkred}y_{i',j',e',c} \>\>\forall \color{darkblue}{\mathit{Touch}}_{i,j,e,i',j',e'}\]
| MIP Model |
|---|
| \[\begin{align}& \sum_{i,j,r} \color{darkred}x_{i,j,k,r} = 1 && \forall k \\ & \sum_{k,r} \color{darkred} x_{i,j,k,r} = 1 && \forall i,j \\ &\color{darkred}y_{i,j,e,c} = \sum_{k,r|\color{darkblue}{\mathit{Sq}}(k,r,e,c)} \color{darkred}x_{i,j,k,r} && \forall i,j,e,c \\ &\color{darkred}y_{i,j,e,\color{darkgreen}{\mathit{White}}}= 1 && \forall \color{darkblue}{\mathit{Border}}_{i,j,e} \\ & \color{darkred}y_{i,j,e,c} = \color{darkred}y_{i',j',e',c} && \forall \color{darkblue}{\mathit{Touch}}_{i,j,e,i',j',e'}\\ & \color{darkred}x_{i,j,k,r} \in \{0,1\} \\ & \color{darkred}y_{i,j,e,c} \in \{0,1\} \end{align}\] |
Notes:
- There is no objective: we only want to find feasible solutions.
- The \(\color{darkred}y\) variable can be declared as continuous between 0 and 1. It will be integer automatically.
- We can reduce the size of the model a bit by being more clever about the set \(\color{darkblue}{\mathit{Sq}}_{k,r,e,c}\). For squares with just one color, there can be just one rotation: the other ones don't add anything. For some squares with 2 colors, like square \(k=4\), there are just two meaningful rotations. The number of elements for \(\color{darkblue}{\mathit{Sq}}\) will decrease from 384 to 324.
All solutions
Note. We can see that square number \(k=1\) (all white edges) is always at the border. This can be proven as follows [4]:
- There are 16 border positions and there are 18 squares with at least one white edge. So exactly two interior cells will contain a square with a white cell.
- Square \(k=1\) in the middle requires two or three interior neighbors with white edges. From 1 we know we only have one such square available.
 |
| A Burroughs B5500 mainframe |
Lingering questions
- How to derive the formula for the number of squares for \(n\) colors?
- How can we reproduce the total number of solutions?
- Can we generate the collection of MacMahon squares automatically, that is using code or by a model?
References
- Percy Alexander MacMahon, https://en.wikipedia.org/wiki/Percy_Alexander_MacMahon
- MacMahon, Percy (1921). New Mathematical Pastimes. Cambridge University Press.
- MacMahon Squares, https://en.wikipedia.org/wiki/MacMahon_Squares
- Feldman, Gary, Documentation of the MacMahon Squares Problem. AIM-012, Stanford Artificial Intelligence Laboratory, 1964, https://exhibits.stanford.edu/stanford-pubs/catalog/nv052jg0055
Appendix: GAMS code
|
$ontext |
- Acronyms are used to make the input table more compact.
- The $onecho constructs are placed at the bottom to keep them out of the way. Notice however that this is a compile-time comment. So even this is at the end of the file, it will be performed before executing any other statements.
The formula for the number of n-colorings up to rotation arises from Burnside's Lemma. The identity element (rotation by 0 degrees) fixes n^4 colorings, rotation by 90 degrees or 270 degrees fixes n colorings each, and rotation by 180 degrees fixes n^2 colorings, yielding (n^4+2n+n^2)/4.
ReplyDelete