Cutting 4 by n n grids into two congruent pieces
Robert Dougherty-Bliss, Natalya Ter-Saakov, Doron Zeilberger · 2025
Read Cutting 4 by n n grids into two congruent pieces by Robert Dougherty-Bliss, Natalya Ter-Saakov, Doron Zeilberger (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-16153.txt.
Introduction
Robert Dougherty-Bliss and two co-authors count the ways to cut a four-by-n grid into two connected pieces that are exact mirror copies of each other in shape and size. The problem follows a puzzle in the French magazine Pour la Science, where Jean-Paul Delahaye had showcased the count for skinnier three-by-two-n rectangles.
The authors solve the wider case with the transfer matrix method, a bookkeeping technique that builds the grid column by column while tracking how the cut edge evolves. From that machinery they compute a generating function, a single formula whose coefficients give the number of valid cuts for every length n. The result turns a hands-on tiling puzzle into exact enumeration.
Catalog record
| CREATOR | Robert Dougherty-Bliss, Natalya Ter-Saakov, Doron Zeilberger |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 19 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-16153
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Cutting 4 by n n grids into two congruent pieces Robert Dougherty-Bliss, Natalya Ter-Saakov, Doron Zeilberger Abstract Pour Jean-Paul Delahaye, avec admiration Introduction In the March 2025 issue of Pour La Science (the French analogue of Scientific American ), in his delightful monthly column [D], Jean-Paul Delahaye described in detail the solution of the following counting problem. In how many ways can you cut a 3\times 2n rectangle consisting of 6n unit squares (in other words a 3\times 2n (colorless) checkerboard) into two connected, congruent pieces? In collaboration with his épouse , Martine Raison, Delahaye used human ingenuity to prove that this number is given explicitly by the beautiful formula 2^{n+1}-n-1 . Here are all twelve ways to divide 3\times 6 rectangles into two congruent, connected parts: We asked ourselves, what about a 4\times n checkerboard? Here are twelve such ways to split a 4\times 6 rectangle into two congruent parts: Now human ingenuity is still necessary , but (most probably) not sufficient . In collaboration with our beloved silicon friends we proved the following deep theorem. Theorem 1 . Let c_{n} be the number of ways of cutting a 4\times n grid into two (connected) congruent pieces. The (ordinary) generating function of c_{n} is \sum_{n=0}^{\infty}c_{n}x^{n}\,=\,{x\left(2x^{8}-4x^{7}+8x^{6}-7x^{5}+3x^{4}+2x^{3}-5x^{2}+x+1\right)\over\left(x-1\right)^{2}\left(x^{4}+3x^{2}-1\right)\left(x^{4}+2x^{2}-1\right)}. The coefficients have the (approximate) asymptotic expansion c_{n}\sim 1.93104(1+0.08417(-1)^{n})(1.8174)^{n}. For the sake of the OEIS the first 30 terms are: \displaystyle 1,3,5,14,22,54,84,197,305,696,1075,2410,3716,8231,12676, \displaystyle 27844,42843,93558,143865,312859,480868,1042624,1602002, \displaystyle 3466064,5324385,11501987,17665729,38119718,58540246,126217718 To our delight, this sequence was not (as of Sept. 4, 2025) in the OEIS. We hope to submit it soon. Our colorful rectangles are very pretty, but it is more convenient to represent such decoupages as 4\times n matrices with entries 0 and 1 , where the value at position ij indicates to which part that entry belongs. For example: \vbox{\hbox{ \hbox to86.16pt{\vbox to57.71pt{\pgfpicture\makeatletter\hbox{\hskip 0.4pt\lower-57.30551pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {{\lx@inpgf@ignorespaces}} {}{{}}{} {{}{}}{{}}{}{}{}{}{{}}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.4961,0.7852,0.9727}\lxSVG@fill\lxSVG@drawpath@unclipped{M 0 0 M 0 0 L 0 -19.69 L 19.69 -19.69 L 19.69 0 Z M 19.69 -19.69}{stroke:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{} {{}{}}{{}}{}{}{}{}{{}}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.4961,0.7852,0.9727}\lxSVG@fill\lxSVG@drawpath@unclipped{M 19.69 0 M 19.69 0 L 19.69 -19.69 L 39.37 -19.69 L 39.37 0 Z M 39.37 -19.69}{stroke:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{} {{}{}}{{}}{}{}{}{}{{}}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.4961,0.7852,0.9727}\lxSVG@fill\lxSVG@drawpath@unclipped{M 39.37 0 M 39.37 0 L 39.37 -19.69 L 59.06 -19.69 L 59.06 0 Z M 59.06 -19.69}{stroke:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{} {{}{}}{{}}{}{}{}{}{{}}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{1,0.8945,0.3672}\lxSVG@fill\lxSVG@drawpath@unclipped{M 59.06 0 M 59.06 0 L 59.06 -19.69 L 78.74 -19.69 L 78.74 0 Z M 78.74 -19.69}{stroke:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{} {{}{}}{{}}{}{}{}{}{{}}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{1,0.8945,0.3672}\lxSVG@fill\lxSVG@drawpath@unclipped{M 78.74 0 M 78.74 0 L 78.74 -19.69 L 98.43 -19.69 L 98.43 0 Z M 98.43 -19.69}{stroke:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{} {{}{}}{{}}{}{}{}{}{{}}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{1,0.8945,0.3672}\lxSVG@fill\lxSVG@drawpath@unclipped{M 98.43 0 M 98.43 0 L 98.43 -19.69 L 118.11 -19.69 L 118.11 0 Z M 118.11 -19.69}{stroke:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{} {{}{}}{{}}{}{}{}{}{{}}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.4961,0.7852,0.9727}\lxSVG@fill\lxSVG@drawpath@unclipped{M 0 -19.69 M 0 -19.69 L 0 -39.37 L 19.69 -39.37 L 19.69 -19.69 Z M 19.69 -39.37}{stroke:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{} {{}{}}{{}}{}{}{}{}{{}}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.4961,0.7852,0.9727}\lxSVG@fill\lxSVG@drawpath@unclipped{M 19.69 -19.69 M 19.69 -19.69 L 19.69 -39.37 L 39.37 -39.37 L 39.37 -19.69 Z M 39.37 -39.37}{stroke:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{} {{}{}}{{}}{}{}{}{}{{}}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.4961,0.7852,0.9727}\lxSVG@fill\lxSVG@drawpath@unclipped{M 39.37 -19.69 M 39.37 -19.69 L 39.37 -39.37 L 59.06 -39.37 L 59.06 -19.69 Z M 59.06 -39.37}{stroke:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{} {{}{}}{{}}{}{}{}{}{{}}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.4961,0.7852,0.9727}\lxSVG@fill\lxSVG@drawpath@unclipped{M 59.06 -19.69 M 59.06 -19.69 L 59.06 -39.37 L 78.74 -39.37 L 78.74 -19.69 Z M 78.74 -39.37}{stroke:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{} {{}{}}{{}}{}{}{}{}{{}}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.4961,0.7852,0.9727}\lxSVG@fill\lxSVG@drawpath@unclipped{M 78.74 -19.69 M 78.74 -19.69 L 78.74 -39.37 L 98.43 -39.37 L 98.43 -19.69 Z M 98.43 -39.37}{stroke:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{} {{}{}}{{}}{}{}{}{}{{}}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{1,0.8945,0.3672}\lxSVG@fill\lxSVG@drawpath@unclipped{M 98.43 -19.69 M 98.43 -19.69 L 98.43 -39.37 L 118.11 -39.37 L 118.11 -19.69 Z M 118.11 -39.37}{stroke:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{} {{}{}}{{}}{}{}{}{}{{}}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.4961,0.7852,0.9727}\lxSVG@fill\lxSVG@drawpath@unclipped{M 0 -39.37 M 0 -39.37 L 0 -59.06 L 19.69 -59.06 L 19.69 -39.37 Z M 19.69 -59.06}{stroke:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{} {{}{}}{{}}{}{}{}{}{{}}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{1,0.8945,0.3672}\lxSVG@fill\lxSVG@drawpath@unclipped{M 19.69 -39.37 M 19.69 -39.37 L 19.69 -59.06 L 39.37 -59.06 L 39.37 -39.37 Z M 39.37 -59.06}{stroke:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{} {{}{}}{{}}{}{}{}{}{{}}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{1,0.8945,0.3672}\lxSVG@fill\lxSVG@drawpath@unclipped{M 39.37 -39.37 M 39.37 -39.37 L 39.37 -59.06 L 59.06 -59.06 L 59.06 -39.37 Z M 59.06 -59.06}{stroke:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{} {{}{}}{{}}{}{}{}{}{{}}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{1,0.8945,0.3672}\lxSVG@fill\lxSVG@drawpath@unclipped{M 59.06 -39.37 M 59.06 -39.37 L 59.06 -59.06 L 78.74 -59.06 L 78.74 -39.37 Z M 78.74 -59.06}{stroke:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{} {{}{}}{{}}{}{}{}{}{{}}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{1,0.8945,0.3672}\lxSVG@fill\lxSVG@drawpath@unclipped{M 78.74 -39.37 M 78.74 -39.37 L 78.74 -59.06 L 98.43 -59.06 L 98.43 -39.37 Z M 98.43 -59.06}{stroke:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{} {{}{}}{{}}{}{}{}{}{{}}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{1,0.8945,0.3672}\lxSVG@fill\lxSVG@drawpath@unclipped{M 98.43 -39.37 M 98.43 -39.37 L 98.43 -59.06 L 118.11 -59.06 L 118.11 -39.37 Z M 118.11 -59.06}{stroke:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{} {{}{}}{{}}{}{}{}{}{{}}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.4961,0.7852,0.9727}\lxSVG@fill\lxSVG@drawpath@unclipped{M 0 -59.06 M 0 -59.06 L 0 -78.74 L 19.69 -78.74 L 19.69 -59.06 Z M 19.69 -78.74}{stroke:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{} {{}{}}{{}}{}{}{}{}{{}}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.4961,0.7852,0.9727}\lxSVG@fill\lxSVG@drawpath@unclipped{M 19.69 -59.06 M 19.69 -59.06 L 19.69 -78.74 L 39.37 -78.74 L 39.37 -59.06 Z M 39.37 -78.74}{stroke:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{} {{}{}}{{}}{}{}{}{}{{}}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0.4961,0.7852,0.9727}\lxSVG@fill\lxSVG@drawpath@unclipped{M 39.37 -59.06 M 39.37 -59.06 L 39.37 -78.74 L 59.06 -78.74 L 59.06 -59.06 Z M 59.06 -78.74}{stroke:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{} {{}{}}{{}}{}{}{}{}{{}}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{1,0.8945,0.3672}\lxSVG@fill\lxSVG@drawpath@unclipped{M 59.06 -59.06 M 59.06 -59.06 L 59.06 -78.74 L 78.74 -78.74 L 78.74 -59.06 Z M 78.74 -78.74}{stroke:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{} {{}{}}{{}}{}{}{}{}{{}}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{1,0.8945,0.3672}\lxSVG@fill\lxSVG@drawpath@unclipped{M 78.74 -59.06 M 78.74 -59.06 L 78.74 -78.74 L 98.43 -78.74 L 98.43 -59.06 Z M 98.43 -78.74}{stroke:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{} {{}{}}{{}}{}{}{}{}{{}}{}\lxSVG@begingroup@{_scopebegin} \color[rgb]{1,0.8945,0.3672}\lxSVG@fill\lxSVG@drawpath@unclipped{M 98.43 -59.06 M 98.43 -59.06 L 98.43 -78.74 L 118.11 -78.74 L 118.11 -59.06 Z M 118.11 -78.74}{stroke:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{}{ {}{}{}{}{ }{ }{ }{ }{ }{ }{ }{ }{ }{ }{ }{ }{}}\lxSVG@begingroup@{_scopebegin} \color[rgb]{0,0,0}\lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 M 0 -78.74 L 118.11 -78.74 M 0 -59.06 L 118.11 -59.06 M 0 -39.37 L 118.11 -39.37 M 0 -19.69 L 118.11 -19.69 M 0 -0.01 L 118.11 -0.01 M 0 -78.74 L 0 0 M 19.69 -78.74 L 19.69 0 M 39.37 -78.74 L 39.37 0 M 59.06 -78.74 L 59.06 0 M 78.74 -78.74 L 78.74 0 M 98.43 -78.74 L 98.43 0 M 118.1 -78.74 L 118.1 0 M 118.11 -78.74}{fill:none} \lx@inpgf@ignorespaces \lxSVG@closescope \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}}}\to\begin{bmatrix}0&0&0&1&1&1\\ 0&0&0&0&0&1\\ 0&1&1&1&1&1\\ 0&0&0&1&1&1\end{bmatrix} Definition 1 . A m\times n matrix M with entries in \{0,1\} that satisfies the rule M_{ij}=1-M_{(m-i)(n-j)} (1) such that the 0 ’s and 1 ’s form exactly two connected components (using north-south-east-west adjacency) is called a Graham matrix . (Note that this rule uses zero indexing.) Why Graham? For one, to honor the great Ron Graham, who advanced discrete mathematics in a substantial way; for another, because the problem is something like breaking apart a graham cracker fairly. Note that if we drop the condition of the two pieces being congruent, and consider only square matrices, then we have the (computationally) challenging problem of the Gerrymander sequence [Sl], beautifully treated in [KKS] and extended in [GJ]. How did we find this beautiful generating function? We asked our computer to show us all these creatures up to n=12 . After some thought, we convinced ourselves that Graham matrices could be recognized by reading them one column at a time; in other words, that they could be recognized by a finite state machine , or a regular grammar . A finite state machine (also called a deterministic finite automata ) is an object which detects words of a language. It reads in words one “symbol” at a time, and uses these symbols to determine a walk on a finite graph. Some states in this graph are marked as accepting , and all others are rejecting . A string of symbols is accepted by