Problem 270: Cutting Squares

Detailed mathematical approach

Problem Summary

A square sheet of paper with integer side \(N\) lies with one corner at the origin and two sides along the axes. A cut is a straight segment between two points with integer coordinates that lie on different sides of the square. Cuts may not cross, although several cuts may end at the same border point, and we keep cutting until no legal cut is left. \(C(N)\) is the number of different final cuttings, where cuttings that differ by a rotation or a reflection count as different. The statement gives \(C(1)=2\) and \(C(2)=30\) and asks for \(C(30)\bmod 10^8\), the remainder of \(C(30)\) after division by \(10^8\). ^[1]

The whole solution in one sentence: a finished cutting is the same as a triangulation of a convex \(4N\)-gon, whose corners stand for the border points in order, with no diagonal joining two points of one side, and these triangulations are counted by splitting off the triangle on one edge, which gives a recurrence over pairs of border points.

Mathematical Approach

We study small squares, show that finished cuttings are such triangulations, and count them with a recurrence, checked by an inclusion–exclusion formula from the literature.

1. The two smallest squares

For \(N=1\) the border points are the four corners. A corner lies on two sides, and two points of one side may not be joined; the segment between them would run along the edge without cutting anything. So the only legal cuts are the two diagonals. They cross, so exactly one of them is made, and then nothing is left to cut: \(C(1)=2\), with two triangles each time.

For \(N=2\) the eight border points are the corners and the side midpoints; each side holds three, no pair lies on two sides, so \(12\) of the \(\binom82=28\) pairs share a side and \(16\) legal cuts remain. In general a side holds \(N+1\) border points, and there are

$$\binom{4N}{2}-4\binom{N+1}{2}=2N(3N-2)$$

legal cuts, \(5280\) for \(N=30\). Each of the \(30\) finished cuttings shown in the statement has \(5\) cuts and \(6\) triangles; Section 5 explains why.

2. Where a cut runs

The square is given by \(0\le x\le N\) and \(0\le y\le N\). A point strictly between \(p\) and \(q\) is \((1-t)\,p+t\,q\) with \(0\lt t\lt 1\); its \(x\)-coordinate equals \(N\) only if those of \(p\) and \(q\) both do, and the same holds for the other three sides. So a point strictly between two points of the square lies on a side only if both points do. Hence a legal cut runs strictly inside the square except at its two endpoints, and it contains no further border point.

3. When two cuts cross

Number the border points \(0,1,\dots,4N-1\) anticlockwise from the origin: \(0,\dots,N\) lie on the bottom side, \(N,\dots,2N\) on the right, \(2N,\dots,3N\) on the top, and \(3N,\dots,4N-1\) and \(0\) on the left, so the corners are \(0\), \(N\), \(2N\) and \(3N\). Two points share a side exactly when both numbers belong to one of these four groups.

The line through a cut from \(p\) to \(q\) leaves the square at \(p\) and \(q\): a point \(r\) of the square beyond \(q\) would put \(q\) strictly between \(p\) and \(r\), and by Section 2 the point \(p\) would lie on a side containing \(q\), which a cut does not allow; the same holds beyond \(p\). So inside the square the line is the cut itself, and it separates the two arcs into which \(p\) and \(q\) divide the rest of the border. A cut with one endpoint on each arc crosses the line inside the square, that is, it crosses the first cut. A cut with both endpoints on one arc, or with one endpoint at \(p\) or \(q\) and the other on an arc, stays on one side of the line and meets the first cut at most at a common endpoint. So two cuts with four different endpoints \(a\lt b\) and \(c\lt d\) cross exactly when \(a\lt c\lt b\lt d\) or \(c\lt a\lt d\lt b\). Only the order of the points around the border matters, together with the rule which pairs share a side.

4. A finished cutting consists of triangles

Non-crossing cuts divide the square into pieces. Inside the square the line of a cut is the cut, so each piece lies on one side of every cut: it is the intersection of the square with half-planes, a convex polygon. Its corners are border points, because cuts meet only there, and each of its edges is a whole cut or a part of a side. In a finished cutting every piece is a triangle with no border points other than its corners.

Indeed, if a piece has at least four corners \(c_1,c_2,c_3,c_4\), in order around it, then \(c_1\) and \(c_3\) do not share a side of the square: the line of that side would meet the piece in one edge containing both, and they would be neighbouring corners. So the segment from \(c_1\) to \(c_3\) is a legal cut that runs inside the piece and crosses no cut. If a piece is a triangle with a further border point \(p\) on an edge, that edge is not a cut by Section 2, so it lies on a side \(S\). Then \(p\) lies strictly inside \(S\) and on no other side, the opposite corner is not on \(S\), and joining the two is again a legal cut inside the piece. In both cases the cutting would not be finished.

5. Every finished cutting has \(4N-3\) cuts

Made one after another, each cut splits one piece into two, so \(d\) cuts give \(d+1\) pieces, here triangles. Each of the \(4N\) steps between neighbouring border points is an edge of exactly one triangle and each cut is an edge of two, so \(3(d+1)=4N+2d\). Every finished cutting therefore has \(4N-3\) cuts and \(4N-2\) triangles; for \(N=30\) these are \(117\) cuts.

6. The auxiliary polygon

For counting we use a strictly convex polygon: put the labels \(0,1,\dots,4N-1\), in the same cyclic order, on the corners of a regular \(4N\)-gon, and call a diagonal of it forbidden if its two labels lie on one side of the square. The other diagonals stand for the legal cuts, and by Section 3 two of them cross exactly when the two cuts do. So a finished cutting gives \(4N-3\) non-crossing diagonals without forbidden ones. Every set of non-crossing diagonals of a convex \(n\)-gon extends to a triangulation, since a face with four or more corners still has a diagonal inside, and every triangulation has exactly \(n-3\) diagonals, ^[2] so these diagonals already form a triangulation. Conversely, take a triangulation without forbidden diagonals. Its diagonals are non-crossing legal cuts, and every other diagonal crosses one of them, since otherwise it would lie inside one triangle and be an edge of it; so every other legal cut crosses one of these cuts, and the cutting is finished.

Therefore \(C(N)\) is the number of triangulations of the convex \(4N\)-gon without forbidden diagonals. Unlike the square, this polygon also has triangulations with forbidden diagonals, which Sections 7, 9 and 10 count.

7. Triangulations without restrictions

In a convex polygon with corners \(0,\dots,n-1\), the edge from \(n-1\) to \(0\) lies in exactly one triangle, whose third corner \(k\) satisfies \(1\le k\le n-2\). The triangle leaves the polygons \(0,\dots,k\) and \(k,\dots,n-1\), which are triangulated independently; one of them is a single edge when \(k=1\) or \(k=n-2\). With \(T_n\) the number of triangulations of an \(n\)-gon and \(T_2=1\),

$$T_n=\sum_{k=1}^{n-2}T_{k+1}\,T_{n-k}\qquad(n\ge3).$$

This is Segner's recurrence for the Catalan numbers; \(T_n\) is the one with index \(n-2\), ^[3] and \(T_2,\dots,T_8\) are \(1,1,2,5,14,42,132\). So the auxiliary octagon of the \(2\times2\) square has \(132\) triangulations, of which only \(30\) avoid the forbidden diagonals.

8. The recurrence with forbidden diagonals

For \(i\lt j\), let \(D(i,j)\) be the number of triangulations without forbidden diagonals of the part of the auxiliary polygon with corners \(i,i+1,\dots,j\), closed by the segment from \(j\) back to \(i\). Then \(D(i,i+1)=1\), as a single edge needs no triangle, and \(D(i,j)=0\) when \(j\ge i+2\), \((i,j)\ne(0,4N-1)\) and \(i,j\) share a side, because the closing segment is then forbidden. For all other pairs

$$D(i,j)=\sum_{k=i+1}^{j-1}D(i,k)\,D(k,j).$$

As in Section 7, the triangle on the closing segment has its third corner \(k\) between \(i\) and \(j\) and leaves the polygons \(i,\dots,k\) and \(k,\dots,j\). The factors \(D(i,k)\) and \(D(k,j)\) count the triangulations of these two parts; a factor is \(1\) when its side of the triangle is an edge of the polygon and \(0\) when that side is a forbidden diagonal. Each valid triangulation determines \(k\), so it is counted exactly once. The segment from \(4N-1\) to \(0\) is an edge, the step from \((0,1)\) to \((0,0)\), so \(C(N)=D(0,4N-1)\). The same subproblems form the classical cubic-time dynamic programme for minimum-weight triangulations, credited to Gilbert and Klincsek, ^[4] with the minimum of weights replaced by a sum of counts.

9. Worked example: the \(2\times2\) square

The border points are \(0=(0,0)\), \(1=(1,0)\), \(2=(2,0)\), \(3=(2,1)\), \(4=(2,2)\), \(5=(1,2)\), \(6=(0,2)\) and \(7=(0,1)\), and the forbidden diagonals \(0\)–\(2\), \(2\)–\(4\), \(4\)–\(6\) and \(0\)–\(6\) join the two corners of one side. Splitting at the third corner \(k\) of the triangle on the edge from \(7\) to \(0\) gives

$$\begin{aligned}C(2)&=\sum_{k=1}^{6}D(0,k)\,D(k,7)\\&=1\cdot19+0\cdot6+1\cdot3\\&\quad+2\cdot1+6\cdot1+0\cdot1=30.\end{aligned}$$

The terms for \(k=2\) and \(k=6\) vanish, since their triangles would need \(0\)–\(2\) or \(0\)–\(6\). The other factors can be checked by hand. In the quadrilateral \(0,1,2,3\) only the diagonal \(1\)–\(3\) is allowed, so \(D(0,3)=1\). The rest follows by inclusion–exclusion: ^[5] take all triangulations of the piece from Section 7, subtract those containing each forbidden diagonal, and add back those containing two of them, which were subtracted twice. Here a prescribed forbidden diagonal cuts off one triangle and leaves a polygon with one corner fewer. So \(D(3,7)=5-2=3\), with the forbidden \(4\)–\(6\), and \(D(0,4)=5-2-2+1=2\), \(D(0,5)=14-5-5+2=6\) and \(D(1,7)=42-14-14+5=19\), with two forbidden diagonals each.

10. An independent formula by inclusion–exclusion

Call a diagonal of the auxiliary polygon that joins two labels two steps apart on one side, such as \(0\)–\(2\), an ear diagonal. It cuts off a triangle whose middle corner, its tip, stands for an inner point of the side. A triangulation with a forbidden diagonal always has an ear diagonal: in a forbidden diagonal with the fewest labels between its endpoints on their side, the triangle on it towards those labels has its third corner among them, and two or more labels in between would make one side of that triangle a shorter forbidden diagonal, so it is itself an ear diagonal.

Two ear diagonals cross exactly when their tips are neighbours on one side, and no triangulation contains two crossing ones. If \(m\) non-crossing ear diagonals are prescribed, the rest is any triangulation of the \((4N-m)\)-gon left after removing their tips, so exactly \(T_{4N-m}\) triangulations contain them. On one side, \(\ell\) tips without neighbours among the \(N-1\) inner points can be chosen in \(\binom{N-\ell}{\ell}\) ways: subtracting \(0,1,\dots,\ell-1\) from their positions in increasing order gives any \(\ell\) of \(N-\ell\) positions. So \(\ell\le h=\lfloor N/2\rfloor\). Ear diagonals of different sides never cross, so the number \(a_m\) of non-crossing sets of \(m\) ear diagonals is the coefficient of \(x^m\) in the fourth power of the polynomial of one side, whose coefficients are these binomial coefficients, and inclusion–exclusion gives

$$C(N)=\sum_{m=0}^{4h}(-1)^m\,a_m\,T_{4N-m},$$

$$\sum_{m=0}^{4h}a_m\,x^m=\Bigl(\sum_{\ell=0}^{h}\binom{N-\ell}{\ell}\,x^\ell\Bigr)^4.$$

For \(N=2\) the inner sum is \(1+x\), so \(a_m=\binom4m\) and

$$\begin{aligned}C(2)&=132-4\cdot42+6\cdot14\\&\quad-4\cdot5+2=30.\end{aligned}$$

This is formula (2.1) of Asinowski, Krattenthaler and Mansour for a quadrilateral whose sides are subdivided by \(N-1\) points each; ^[6] their table and the OEIS entry A282733 ^[7] start with \(2,30,604,12168,238848,4569624\).

11. Growth and remainders

Further values are \(C(5)=238848\), \(C(6)=4569624\), \(C(7)=85553528\) and \(C(8)=1573583616\); for \(3\le N\le10\) each step multiplies the count by roughly \(18\) to \(20\). \(C(N)\) exceeds \(2^{64}\) from \(N=17\) on, and \(C(30)\) has \(37\) digits. The remainder of a sum or a product depends only on the remainders of its parts, ^[8] and the recurrence only adds and multiplies, so every \(D(i,j)\) can be kept modulo \(10^8\); the last entry is then \(C(N)\bmod10^8\).

How the Code Works

The C++ program ^[9] starts in main, which reads the optional arguments -n N, the side length with default \(30\), and --no-validate. Unless the checks are switched off, run_validation computes \(C(1),\dots,C(4)\) and stops with an error message if they differ from \(2\), \(30\), \(604\) and \(12168\). Then count_triangulations computes the count, and main prints it.

count_triangulations returns \(0\) for \(N\le0\). Otherwise build_boundary lists the \(4N\) border points as Point values in the order of Section 3. The matrix allowed marks the pairs that the recurrence may use: the steps \((i,i+1)\) and \((0,4N-1)\) of the border, which are the edges of the auxiliary polygon, and every pair for which same_side is false. That function tests whether both points have \(y=0\), both \(y=N\), both \(x=0\) or both \(x=N\), so these pairs are exactly the legal cuts. The table dp holds \(D(i,j)\bmod10^8\). The entries dp[i][i+1] start at \(1\), and the others are filled by increasing length \(j-i\), from \(2\) to \(4N-1\), so the entries on the right of the recurrence, which are shorter, are already final. A pair that is not allowed gets \(0\), as a forbidden diagonal of Section 8; for an allowed pair the loop over \(k\) adds the products of dp[i][k] and dp[k][j], skipping those with a zero factor. The result is dp[0][m-1] with \(m=4N\), which is \(C(N)\bmod10^8\) by Sections 8 and 11. In C++ the body of these loops is the lambda compute_range, which fills the entries of one length for a range of starting points \(i\).

The C++ table holds 32-bit unsigned entries, which suffice because \(10^8\lt2^{32}\). Each product of two entries is below \(10^{16}\) and is added to a 64-bit unsigned sum. Inside the loop the sum is reduced modulo \(10^8\) whenever it reaches \(10^{16}\), so it stays below \(2\cdot10^{16}\), far from \(2^{64}\approx1.8\cdot10^{19}\); after the loop its remainder modulo \(10^8\) is stored. Python and Java reduce after every addition: Python's integers have no size limit, and Java's long holds the products, which are below \(10^{16}\lt2^{63}\). Python uses tuples and lists of lists; Java names the functions buildBoundary, sameSide and countTriangulations and uses boolean[][] and long[][] tables. Their entry points, solve and main, compute only \(N=30\), without checks.

Complexity and Verification

For \(N=30\) there are \(m=120\) border points and \(7140\) pairs, of which \(5400\) are allowed: the \(5280\) legal cuts and the \(120\) steps of the border. The loop over \(k\), once for each \(k\) between \(i\) and \(j\) of an allowed pair, runs \(260308\) times, against \(\binom{120}3=280840\) if no pair were forbidden, and \(111364\) of these steps multiply two nonzero factors. In general there are \(O(m^2)\) pairs with at most \(m\) choices of \(k\) each, so the time is \(O(N^3)\), and the two \(m\times m\) tables take \(O(N^2)\) memory. On a desktop computer each of the three programs took well under a tenth of a second, start-up included.

Besides the checks of \(C(1),\dots,C(4)\) in the C++ program, we verified the following for this article; these checks are not part of the published solutions.

• The three programs print the same value for \(N=30\), and the C++ program with -n 5, -n 6 and -n 7 prints the values of Section 11.
• An exact implementation of the recurrence, without remainders, gives the same remainder for \(N=30\) and all values quoted here.
• A geometric brute force, which uses none of Sections 3 to 8, takes the legal cuts as segments between integer points, decides crossings with exact orientation tests, and lists all maximal sets of pairwise non-crossing cuts with the Bron–Kerbosch algorithm. ^[10] For \(N=1,\dots,6\) it finds \(2\), \(30\), \(604\), \(12168\), \(238848\) and \(4569624\) finished cuttings, each with exactly \(4N-3\) cuts.
• The formula of Section 10 agrees with the recurrence, in exact integers, for every \(N\le30\), and listing all \(132\) triangulations of the octagon and all \(16796\) of the \(12\)-gon confirms the ear-diagonal claim for \(N=2\) and \(N=3\).

Footnotes and References

The references below supply the background facts; the reduction to restricted triangulations, the recurrence and all numbers are derived or computed in this article.

1. Project Euler 270 — Cutting Squares. The official statement: straight cuts join integer points on different sides of an N × N square, may not cross but may meet at border points, and continue until no legal cut is left; C(N) counts the ways, reflections and rotations distinct, C(1) = 2 and C(2) = 30, and the task asks for C(30) mod 10⁸.
2. Wikipedia — Polygon triangulation. A triangulation of a simple polygon with n vertices that adds no vertices has n − 2 triangles separated by n − 3 diagonals, and a convex n-gon has as many triangulations as the (n − 2)nd Catalan number.
3. Wikipedia — Catalan number. A convex polygon with n + 2 sides has Cₙ triangulations; the Catalan numbers satisfy Segner's recurrence C₀ = 1, Cₙ₊₁ = C₀Cₙ + C₁Cₙ₋₁ + ⋯ + CₙC₀ and begin 1, 1, 2, 5, 14, 42, 132, …
4. Wikipedia — Minimum-weight triangulation. A cubic-time dynamic program for polygons, reported independently by Gilbert (1979) and Klincsek (1980), solves one subproblem for each diagonal from vertex i to vertex j by choosing the vertex k that completes the triangle on it.
5. Wikipedia — Inclusion–exclusion principle. The number of elements of a finite set S that lie in none of the subsets A₁, …, Aₙ is |S| − Σ|Aᵢ| + Σ|Aᵢ ∩ Aⱼ| − ⋯ + (−1)ⁿ|A₁ ∩ ⋯ ∩ Aₙ|.
6. A. Asinowski, C. Krattenthaler and T. Mansour — Counting triangulations of some classes of subdivided convex polygons (arXiv:1604.02870). The paper counts the triangulations tr(k, r) of a convex k-gon whose sides are each subdivided by r − 1 points. Through kr points in convex position, its Observations 1 and 2 exclude the diagonals joining two points of one side, equivalently those at distance 2 on a side; its formula (2.1) is the sum of Section 10 with k = 4 and r = N, and its Table 1 lists tr(4, r) = 2, 30, 604, 12168, 238848, 4569624 for r ≤ 6.
7. OEIS A282733. Number of triangulations of a convex 4-gon in the plane each of whose sides is subdivided by n points; with offset 0 its terms 2, 30, 604, 12168, … are C(1), C(2), C(3), …, and the entry gives a(n) = tr(4, n + 1) from the paper of reference [6].
8. Wikipedia — Modular arithmetic. Congruence is compatible with addition and multiplication: if a₁ ≡ b₁ and a₂ ≡ b₂ (mod m), then a₁ + a₂ ≡ b₁ + b₂ and a₁a₂ ≡ b₁b₂ (mod m).
9. C++ — Euler270.cpp. The linked immutable C++ revision contains build_boundary, same_side, count_triangulations and run_validation with the checks C(1) = 2, C(2) = 30, C(3) = 604 and C(4) = 12168. It is the implementation record for this article.
10. Wikipedia — Bron–Kerbosch algorithm. Published by Coenraad Bron and Joep Kerbosch in 1973, it lists all maximal cliques of an undirected graph, here the graph of legal cuts in which two cuts are joined when they do not cross; a variant with pivoting prunes the search.