Welcome to our community

Be a part of something great, join today!

Number of ways to divide a square grid in half

HapaxOromenon

New member
Jun 16, 2019
3
Consider a dotted square grid with $4$ rows and $4$ columns, as shown: Kv3LU.jpg
By drawing a series of connected straight lines from dot to dot, it is possible to divide the square (which effectively has side length $3$) into two parts of equal area. One way of doing this is as shown: uitQp.jpg
Other examples of ways of doing this are: 5H36O.jpg; IMG_20190617_022915__01.jpg; and IMG_20190617_023616__01.jpg.

The question I am investigating is how many such ways there are in total, or if such a calculation is too difficult, I would at least like to have a systematic way of listing all of the ways. But I'm not sure really where to start. Any assistance would be greatly appreciated.
 

Opalg

MHB Oldtimer
Staff member
Feb 7, 2012
2,678
Consider a dotted square grid with $4$ rows and $4$ columns, as shown:
By drawing a series of connected straight lines from dot to dot, it is possible to divide the square (which effectively has side length $3$) into two parts of equal area. One way of doing this is as shown:
Other examples of ways of doing this are: ; ; and .

The question I am investigating is how many such ways there are in total, or if such a calculation is too difficult, I would at least like to have a systematic way of listing all of the ways. But I'm not sure really where to start. Any assistance would be greatly appreciated.
Hi HapaxOromenon , and welcome to MHB!
This looks like an interesting problem, and I'm not sure whether it has a straightforward solution. But first, we need to be sure what you are trying to count. You want to partition the square grid into two parts, and you say that these parts should have the same area. In all the examples that you show, the two parts are congruent. So my first question is this: Would you allow a partition like this
\begin{tikzpicture}
[scale=2]\foreach \i in {0,...,3}
{
\draw[thin,dotted] (\i,0) -- (\i,3) ;
\draw[thin,dotted] (0,\i) -- (3,\i) ;
\foreach \j in {0,...,3}
\fill [black,opacity=.5] (\i,\j) circle (2pt) ; }
\draw[thick] (0,2) -- (2,2) -- (2,1) -- (3,0) ;

\end{tikzpicture}
where the two parts have the same area (4.5 square units) but they have different shapes?

The second question is whether you would consider two partitions to be the same if one of them is just a rotation or reflection of the other one. For example, do you consider these partitions
\begin{tikzpicture}
[scale=2]\foreach \i in {0,...,3}
{
\draw[thin,dotted] (\i,0) -- (\i,3) ;
\draw[thin,dotted] (0,\i) -- (3,\i) ;
\foreach \j in {0,...,3}
\fill [black,opacity=.5] (\i,\j) circle (2pt) ; }
\draw[thick] (0,2) -- (1,2) -- (2,1) -- (3,1) ;

\end{tikzpicture} ................ \begin{tikzpicture}
[scale=2]\foreach \i in {0,...,3}
{
\draw[thin,dotted] (\i,0) -- (\i,3) ;
\draw[thin,dotted] (0,\i) -- (3,\i) ;
\foreach \j in {0,...,3}
\fill [black,opacity=.5] (\i,\j) circle (2pt) ; }


\draw[thick] (2,3) -- (2,2) -- (1,1) -- (1,0) ;
\end{tikzpicture}
to be the same, or different?
 

HapaxOromenon

New member
Jun 16, 2019
3
1) Yes, I would count this as a valid cut.
2) I would consider them to be different.
 

Opalg

MHB Oldtimer
Staff member
Feb 7, 2012
2,678
Each cut must start and finish at points on the boundary of the grid. There are two sorts of boundary points, namely the four corners of the grid, and the eight points on the edges that are not corners (I'll call these edge points).

Trying to find a systematic way to count the number of possible cuts, I split them into three classes:
1. cuts that go from corner to corner;
2. cuts that go from a corner to an edge point;
3. cuts that go between two edge points.

For the first class, there are nine cuts between the northwest and southeast corners of the grid, as in this diagram

diagram1.jpg.

Rotating those grids through a right angle, you get the same number of cuts between the northeast and southwest corners of the grid. So altogether there are 18 cuts of class 1.

For the second class, there are ten cuts starting at the northwest corner of the grid and ending at an edge point, as in this diagram

diagram2.jpg.

Rotating them, you get the same number of cuts starting at each of the other corners of the grid. So there are 40 cuts of class 2.

That leaves class 3, the cuts going from an edge point to a point on the opposite edge. I found 17 cuts starting from the point immediately below the northwest corner of the grid, as in this diagram

diagram3.jpg

Flipping each of these about a horizontal axis, you get the same number of cuts starting from the point immediately above the southwest corner of the grid. So there are 34 cuts of class 3 going from side to side of the grid. Rotating them through a right angle, you get another 34 cuts of class 3 between the top and bottom of the grid. So altogether there are 68 cuts of class 3.

Thus the overall total number of cuts is 18 + 40 + 68 = 126 (unless I have overlooked any other possible cuts).