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?


  • $\begingroup$ There's a vertical symmetry. If you check one set of choices, you've also checked the symmetric choice. So you can divide your number of possible combinations by 2. There's a cyclical symmetry as well. If you've checked a set of choices, you've implicitly checked the circular shift of that set of choices as well. So you could also take advantage of that. $\endgroup$
    – NicNic8
    Jun 4 '20 at 1:40
  • $\begingroup$ This is combinatorics, not geometry. If $x_1$, $x_2$, $x_3$, and $x_4$ are the $x$ coordinates for each row, the question is how many combinations there are such that $x_1 + x_2 + x_3 + x_4 = 8$, when each can have value $0$, $1$, $2$, $3$, or $4$. The answer is 85, by the way; that includes all symmetric cases. $\endgroup$
    – None
    Jun 4 '20 at 3:16
  • $\begingroup$ @None $85$ is far too many. See my answer below. $\endgroup$
    – K.defaoite
    Jun 4 '20 at 3:40
  • $\begingroup$ @K.defaoite: Check your solutions. Your area calculation is incorrect, and won't return the obvious (2, 2, 2, 2) one, for example. In particular, for OP, n = 5, not 4, because the set of possible coordinates is 0, 1, 2, 3, and 4. Which in Python is produced by range(0, 5). $\endgroup$
    – None
    Jun 4 '20 at 4:08
  • 3
    $\begingroup$ @None: It looks to me like the coordinates have to be $0,1,2,3$ as there are only four dots per row. It would be more consistent to start counting the rows at $0$ as well. Then the solutions for $n=4$ are the cases $x_0+2x_1+2x_2+x_3=9$ because the center dots pull the area over a width of $2$ while the edge ones pull the area with width $1$. $\endgroup$ Jun 4 '20 at 4:23

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$

  • $\begingroup$ This is a marvelous simplification. As a curiosity, do you have any idea how we might determine the number of solutions for the general $n \times n$ case? I assume it will involve things such as partition numbers and whatnot and will likely be quite complicated. $\endgroup$
    – K.defaoite
    Jun 4 '20 at 5:01
  • $\begingroup$ @K.defaoite: Perhaps you can get Ross Millikan to expand his answer about the general case. $\endgroup$
    – Blue
    Jun 4 '20 at 5:08

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:

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)
  • 1
    $\begingroup$ If I'm not mistaken, $a_n$ in the definition of $A$ should be $a_{n-1}$. If you have a $n$ by $n$ lattice, there are only $n-1$ trapezoids inbetween. Which also corresponds nicely to the indices used in the sum for $A_L$. $\endgroup$
    – HSN
    Jun 4 '20 at 12:39
  • $\begingroup$ Oh yes, how silly of me. Thanks, I'll correct it. $\endgroup$
    – K.defaoite
    Jun 4 '20 at 13:01
  • 2
    $\begingroup$ If $p_n(x) = (x^n-1)/(x-1)$, then the number of solutions to equation (1) is the coefficient of $x^{(n-1)^2}$ in the degree-$2(n-1)^2$ polynomial $q_n(x) = p_n(x)^2p_n(x^2)^{n-2}$. All the coefficients of $q_n$ are nonnegative, and so this number of solutions is $\le q_n(1) = n^n$. It might well be possible to show that the central coefficient is the largest coefficient, which would show that the number of solutions is $\ge n^n/[2(n-1)^2+1]$. When $n$ is large these are pretty tight bounds. (The coefficient in question can be written as a complicated sum with binomial coefficients as well.) $\endgroup$ Jun 4 '20 at 17:37
  • $\begingroup$ I'm assuming this has something to do with "generating functions" or something. Fantastic stuff. $\endgroup$
    – K.defaoite
    Jun 5 '20 at 0:19

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}$

  • $\begingroup$ Hi, nice answer. What does the variable $k$ mean in "...for a given $k$, there are..." And how did you come up with $\max (k+1,2n-1-k)$? $\endgroup$
    – K.defaoite
    Jun 4 '20 at 5:06
  • 1
    $\begingroup$ $k=x_0+x_{n-1}$. If $k$ is small, each summand can range from $0$ to $k$, so there are $k+1$ ways to make the sum. If $k$ is large, it ranges from $n-1-k$ to $n-1$, but it should be min not max. I'll fix. $\endgroup$ Jun 4 '20 at 13:33

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


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]$.

graph of the number of paths for increasing n

  • $\begingroup$ Coming back to this months later. Nice answer and thanks for the mention. $\endgroup$
    – K.defaoite
    Jan 10 at 0:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.