How many paths are possible such that the area of the square cut off is exactly half the area of the entire square?

Question

A vertical polygonal path will be formed by picking one point from each row of the four by four grid of points below (Fig. 1), and then connecting these points sequentially from top to bottom. The area of the grid to the left of the polygonal path will then be shaded. For how many four-point selections will the vertical polygonal path result in exactly half of the grid's area being shaded? One example is given in Figure 2.

I want to find a better way than bashing the $4^4$ ways of making a line?

Thanks!

Answer 1

As noted by others, we seek to solve $$a + 2 b + 2 c + d = 9 \tag{$\star$}$$ for $a$, $b$, $c$, $d$ the "coordinates" in $\{0,1,2,3\}$ for the chosen dots in each row. (Equivalently, these are the lengths of the bases of the three (possibly-degenerate) trapezoids comprising the shaded area, with $b$ and $c$ each belonging to two such trapezoids.)

We observe that

• $a+d$ must be odd.
• Since $a \neq d$, we may consider $a<d$ to get half of the solutions; the other half come from reflecting these across the figure's horizontal axis.

The cases are then quite straightforward to enumerate:

$$\begin{array}{c:c:c:c:c} a+d & b+c & (a,d) & (b,c) & \text{# solns} \\\hline 1 & 4 & (0,1) & (1,3), (2,2), (3,1) & 1\times 3=3\\ 3 & 3 & (0,3), (1,2) & (0,3), (1,2), (2,1), (3,0) & 2\times 4 = 8 \\ 5 & 2 & (2,3) & (0,2), (1,1), (2,0) & 1\times 3=3 \end{array}$$

Hence, there are $14$ solutions with $a<d$, and therefore $28$ solutions in all. $\square$

Answer 2

Let us consider a grid with $n \times n$ dots. Number the rows from $0$ to $n-1$ and the dots in a row from $0$ to $n-1$. Let the selected dots be $x_0, x_1, \ldots x_{n-1}$. The area requirement is $$x_0+x_{n-1}+2\sum_{i=1}^{n-2}x_i=(2n-2)\frac{n-1}2=(n-1)^2$$ because the dots in the middle pull the area twice as much as the ones at the ends. The sum $x_0+x_{n+1}$ can range from $0$ to $2n-2$ and for a given value $k$ there are $\min (k+1,2n-1-k)$ ways to make the sum. We are only interested in sums that have the same parity as $n-1$ so that twice the sum of the other $x$'s is even. Having chosen $k$ with the proper parity, we are looking for weak compositions of $\frac 12((n-1)^2-k)$ into $n-2$ pieces of at most $n-1$. This is the coefficient of $x^{\frac 12((n-1)^2-k)}$ in $\left(\frac{x^n-1}{x-1}\right)^{n-2}$

Answer 3

So your problem boils down to determining the number of solutions of a Diophantine equation (which is an area of mathematics I know very little about.) I'm going to present a solution for an $n\times n$ lattice. Let's get started with some definitions. Essentially, the process here is selecting a point from each row. I'll give the selection in the $k$th row a "left index", $x_k$ and a "right index", $y_k$. These indices start from $0$, that is, the "left index" of the leftmost point is $0$ and the "right index" of the leftmost point is $n-1$. So in your Fig. 2, the left indices are $x_1=2, x_2=0, x_3=2, x_4=3$. And the right indices are $y_1=1, y_2=3,y_3=1,y_4=0.$ It is always true that $$x_k+y_k=n-1.$$ Hopefully this is clear enough, but please comment if you need additional clarification.

To solve this problem, I'm going to define an area function. The area function is the sum of the areas of trapezoids formed by pairs of points. That is, $$A=a_1+a_2+...+a_{n-1}$$ Where $a_1$ is the area between the first and second row, $a_2$ the area between the second and third, and so on. WLOG, I'll call the distance between adjacent lattice points $1$ (so then, the total area of the lattice is $(n-1)^2$). Thus, $a_k= \frac{1}{2}(b_k+b_{k+1})$, where $b_k$ is the $k$th trapezoid "base". Therefore the left hand area is $$A_L=\sum_{i=1}^{n-1}{\frac{1}{2}(x_i+x_{i+1})} \equiv \frac{S}{2}$$ And the right hand area is $$A_R=\sum_{i=1}^{n-1}{\frac{1}{2}(y_i+y_{i+1})}$$ However this can be restated as $$A_R=\sum_{i=1}^{n-1}{\frac{1}{2}(n-x_i-1+n-x_{i+1}-1)}$$ $$A_R=\sum_{i=1}^{n-1}{\frac{1}{2}((2n-2)-x_i-x_{i+1})}$$ $$A_R=\sum_{i=1}^{n-1}{n-1}+\sum_{i=1}^{n-1}{-x_i-x_{i+1}}$$ $$A_R=(n-1)^2-\frac{S}{2}.$$ As a sanity check, the area of the entire lattice should be equal to $A_L+A_R$, and it is indeed true that $$A_L+A_R=\frac{S}{2}+(n-1)^2-\frac{S}{2}=(n-1)^2$$ Which is consistent. Now, for the left and right hand areas to be equal, $$A_L=A_R \implies S=(n-1)^2$$ Recalling the definition of $S$, $$\sum_{i=1}^{n-1}{x_i+x_{i+1}}=x_1+x_n+2\sum_{i=2}^{n-1}{x_i}=(n-1)^2.\tag{1}$$ This is a Diophantine equation subject to the constraints that $x_1,...,x_n \in \{0,1,2,...,n-1\}.$ For the $n=4$ case, this is $$x_1+x_4+2x_2+2x_3=9$$ Which has $28$ solutions. This formulation is consistent as it produces $2$ solutions for the $n=2$ case and $5$ solutions for the $n=3$ case. This can be verified easily on the diagram with pencil and paper.

Unfortunately, not only does my formula not account for rotations, but I also don't know how many solutions it will have given the number $n$ (combinatorics people, help!) but hopefully this is a good amount of insight to get going.

FYI: the $n=4$ case was checked with the following Python code:

n=4
X=(0,0,0,0)
solutions=[]
for x1 in range(0,n):
    for x2 in range(0,n):
        for x3 in range(0,n):
            for x4 in range(0,n):
                X = (x1,x2,x3,x4)
                S=x1+x4+2*(x2+x3)
                if(S==(n-1)**2):
                    solutions.append(X)
print(str(solutions))
print(len(solutions))

Answer 4

Here are some results for general $n \times n$ grids. We already know from @K.defaoite that we are counting the number of solutions to the Diophantine equation $$ x_1+x_n+2\sum_{i=2}^{n-1}{x_i}=(n-1)^2.\tag{1} $$ where $x_1,...,x_n \in \{0,1,2,...,n-1\}$. This can easily be done using Generating Functions. We will construct a function which when expanded as a power series contains the desired result as a coefficient.

Let us first solve it when $n=4$ as in the original question. Then the possible values of $x_1$ and $x_4$ will both be represented by an instance of $(x^0+x^1+x^2+x^3)$ each while $2x_2$ and $2x_3$ will be represented by an instance of $(x^0+x^2+x^4+x^6)$ each as they can take values in $\{0,2,4,6\}$. Now to finish the job we multiply them all together. $$ (x^0+x^1+x^2+x^3)(x^0+x^1+x^2+x^3)(x^0+x^2+x^4+x^6)(x^0+x^2+x^4+x^6)= $$ $$ x^{18} + \cdots + 26 x^{10} + 28 x^9 + 26 x^8 + \cdots + 2 x + 1 $$ And by inspecting the coefficient of $x^9$ (as the original equation was supposed to be equal to $(4-1)^2=9$) we find the answer of $28$. This may seem like magic if you've never used generating functions before but it is pretty straightforward if you have.

Another way to write the function we expanded is $$ \left(\frac{1-x^4}{1-x}\right)^2 \left(\frac{1-x^{2*4}}{1-x^2}\right)^{2}. $$ If we wanted the answer for any other $n \geq 2$ we would use the following equation $$ \left(\frac{1-x^n}{1-x}\right)^2 \left(\frac{1-x^{2n}}{1-x^2}\right)^{n-2} $$ and inspect the coefficient of $x^{(n-1)^2}$ in its expansion. This can be done quickly on a computer. Here is an example with SageMath.

for n in range(2, 100):
    var('x')
    s = (((1-x^n)/(1-x))^2)*(((1-x^(2*n))/(1-x^2))^(n-2))
    k = (n-1)^2
    ser = s.series(x, k+1)
    print(ser.coefficient(x, k))

and here is the output

2
5
28
233
2496
34717
560792
10837745
234252640
5793308021
156829052348
4726775956663
153725030521440
5465340128934701
207520380820530352
8502015187163965793
369123177825198911808
17123433665509400298589
836649901974035508157100
43348430749083909825712121
2353933484464410773323930872
134730537277335339769809734135
8049384820904174742127156057768
504393692364251496016719795536853
32879032642089128552704282327732976
2238725691854400035129253185953365227
158111305758902429977336709637800145952
11624065252392903584725054838859224757977
884189366718104321772403698288457861982528
69804656785211699421056362895559908322127565
5689418064795857100326697159921198110924552032
480060539564928288772207576142006411568125122753
41738359962436979492537449536886951761964402359424
3748464033259661570016932840376348717586107245206365
346293506117970320315192404706773692417058306380423756
32980988181308172817382996596598004172288299855983467225
3226245205406066142779370598468738619957941594252888309112
324792052746228804499921717738301634158066136755688312147493
33537946512952815133040650392227058194229847507800119373138480
3558514361969656010544761319426617589034969193841754147483741407
386803278583641913213149583742616931272112457744719951173455389080
43142786766448768150473624655321822456482576183104164023394006636115
4924146629158580819661147694336186090530672837797064343804969064319796
575976109103153874358876516329317957451189708408904914867682142656587495
68871751860970999306038816228636561542826926773797502353867126451381895296
8430107709811914445224261675123076405779248666861154646672658614153410723891
1053862919516715510536731750514321557506717369926264499151489536187134901408272
134722127425863450557215425915261486581507399707340453032906491340158697923933705
17574437128722929195115404532648886947173346005152512175123132787232928984104191200
...

And finally, here is a diagram of the values where the x-axis is $n$ while the y-axis is the (natural) logarithm of the number of paths. The bounds mentioned by @GregMartin are also included: the red line is $x^x$ and the green line is $x^x / [2(x-1)^{2}+1]$.