Number of ways to divide a square grid in half

  • MHB
  • Thread starter HapaxOromenon
  • Start date
  • Tags
    Grid Square
In summary, the question asks how many ways a square grid can be partitioned into two parts with the same area, and the answer is that there are 126 possible cuts.
  • #1
HapaxOromenon
3
0
Consider a dotted square grid with $4$ rows and $4$ columns, as shown: View attachment 9092
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: View attachment 9093
Other examples of ways of doing this are: View attachment 9094; View attachment 9095; and View attachment 9096.

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.
 

Attachments

  • Kv3LU.jpg
    Kv3LU.jpg
    57.1 KB · Views: 85
  • uitQp.jpg
    uitQp.jpg
    160.9 KB · Views: 94
  • 5H36O.jpg
    5H36O.jpg
    52.6 KB · Views: 87
  • IMG_20190617_022915__01.jpg
    IMG_20190617_022915__01.jpg
    167.6 KB · Views: 94
  • IMG_20190617_023616__01.jpg
    IMG_20190617_023616__01.jpg
    172.8 KB · Views: 96
Physics news on Phys.org
  • #2
HapaxOromenon said:
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
[TIKZ] [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) ;
[/TIKZ]
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
[TIKZ] [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) ;
[/TIKZ] ... [TIKZ] [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) ;[/TIKZ]
to be the same, or different?
 
  • #3
1) Yes, I would count this as a valid cut.
2) I would consider them to be different.
 
  • #4
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

View attachment 9106.

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

View attachment 9107.

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

View attachment 9105

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).
 

Attachments

  • diagram3.jpg
    diagram3.jpg
    14.7 KB · Views: 80
  • diagram1.jpg
    diagram1.jpg
    6.3 KB · Views: 77
  • diagram2.jpg
    diagram2.jpg
    13.3 KB · Views: 83

FAQ: Number of ways to divide a square grid in half

1. How many ways can a square grid be divided in half?

The number of ways to divide a square grid in half depends on the size of the grid. For example, a 2x2 grid can be divided in half in 2 ways, while a 3x3 grid can be divided in half in 6 ways. In general, for an n x n grid, there are (n^2)!/(2^n * n!) ways to divide it in half.

2. Does the number of ways to divide a square grid in half change if the grid is rotated?

No, the number of ways to divide a square grid in half remains the same even if the grid is rotated. This is because rotation does not change the number of rows or columns in the grid, which is what determines the number of ways to divide it in half.

3. Can a square grid be divided in half in an odd number of ways?

No, a square grid can only be divided in half in an even number of ways. This is because each division creates two equal halves, so there must always be an even number of divisions.

4. Are all the ways to divide a square grid in half symmetrical?

No, not all ways to divide a square grid in half are symmetrical. For example, if the grid is divided horizontally, the two halves will be symmetrical, but if it is divided diagonally, the two halves will not be symmetrical.

5. Is there a limit to the size of a square grid that can be divided in half?

No, there is no limit to the size of a square grid that can be divided in half. However, as the size of the grid increases, the number of ways to divide it in half also increases at a rapid rate, making it difficult to calculate manually for very large grids.

Similar threads

Back
Top