How many paths are possible such that the area of the square cut off is exactly half the area of the entire square? 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!
 A: 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$
A: 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}$
A: 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))

