Mirroring the Slopes (Count 'em All 19!)

First, we classify the quadrilaterals into five cases. The formula for the number of each is given

Vertical symmetric trapezoids
$F_1(n)=\frac{1}{2}(n-1)n$
Vertical non-symmetric trapezoids
$F_2(n)=\frac{2}{3}(n-1)n(n+1)$
Horizontal non-symmetric trapezoids
$F_3(n)=\frac{1}{3}(n-1)n(n+1)$
Irregular quadrilaterals
$F_4(n)=(n-1)n$
Rectangles
$F_5(n)=\frac{1}{6}(n-1)n(n+1)^2$

When added all together, the final formula works out to

$F(n)=\frac{1}{6}(n-1)n(n+4)^2$

So that the the first few values are $0,12, 49, 128$ , and

$F(30)=167620$

The right arrow grid is made from 2 individual slope grids. The number of quadrilaterals in each of the 2 slope grids is $\frac{a(a-1)(a+1)(a+10)}{24}$

Here's a quick sketch of a proof for this formula, you can see more details of this proof in my solution to Count 'em Slopes (Count 'em All 17!) , if you've already seen it, you may safely skip this part. :D

Proof:

Before we dive into slope grids, I shall prove first that the number of quadrilaterals in an $a\times a$ staircase grid is $\frac{a(a+1)(a+2)(a+3)}{24}$

Suppose the number of quadrilaterals in an $a\times a$ staircase grid is $Q_a$ , we will try to find $Q_{a+1}$ .

To increase $a$ by 1, we simply add $a+1$ squares to the hypotenuse (the yellow squares), the newly formed quadrilaterals must contain one of the yellow squares as its top-right corner square. If a quadrilateral's top-right corner square lies on a yellow square that is $i$ units away from the left boundary, then it must be $a-i$ units away from the bottom boundary, and the number of possible locations for its bottom-left corner square is $(i+1)(a-i+1)$ .

Therefore, $Q_{a+1}=Q_a+\displaystyle \sum_{i=0}^a(i+1)(a-i+1)=Q_a+\frac{a^3+6a^2+11a+6}{6}$ .

Solving this recurrence relation with the initial condition $Q_1=1$ , we get that $Q_a=\frac{a(a+1)(a+2)(a+3)}{24}$ . $_\square$

Back to slope grids, we observe that an $a\times a$ slope grid consists of an $(a-1)\times(a-1)$ staircase grid with $a$ triangles patched along its hypotenuse. The number of quadrilaterals in the $(a-1)\times(a-1)$ staircase grid is $\frac{a(a-1)(a+1)(a+2)}{24}$ .

We now just need to count the remaining trapeziums.

To construct a trapezium, we choose a certain length of the slanted edge of the slope grid. The number of ways to choose a slanted edge of length $i$ $(i\in\mathbb{Z^+},\,i\leqslant a)$ is $a-i+1$ . Then, we need either a matching left edge for the trapezium or a matching bottom edge for the trapezium. The total number of ways to do so with the chosen slanted edge of length $i$ is $a-i$ . Therefore, the total number of trapeziums is $\displaystyle\sum_{i=1}^{a}(a-i)(a-i+1)=\frac{a(a-1)(2a-1)}{6}+\frac{a(a-1)}{2}$ .

Therefore, the number of quadrilaterals in an $a\times a$ slope grid is $\frac{a(a-1)(a+1)(a+2)}{24}+\frac{a(a-1)(2a-1)}{6}+\frac{a(a-1)}{2}=\frac{a(a-1)(a+1)(a+10)}{24}$ . $_\square$

The total number of quadrilaterals in the two slope grids is $2\times\frac{a(a-1)(a+1)(a+10)}{24}=\frac{a(a-1)(a+1)(a+10)}{12}$ .

It now remains to count the number of "crossover" quadrilaterals (quadrilaterals that cross the common boundary of both slope grids). We'll construct the crossover quadrilaterals by picking one square or triangle from the top slope grid as its top-right corner square or triangle, and one square or triangle from the bottom slope grid as its bottom-left corner square or triangle (if any of its corners are triangles, the resulting quadrilateral would be a trapezium).

Consider picking one square or triangle in the $i$ -th column $(i\in\mathbb{Z^+})$ from the left of the top slope grid where $1\leqslant i\leqslant a-1$ . The height of that column is $a-i+1$ .

Now we pick its corresponding bottom-left corner square or triangle from the bottom slope grid so that it forms a valid quadrilateral. Valid bottom-left corners consist of the corresponding $i\times(a-i)$ squares in the bottom slope grid, plus the additional $i$ triangles below the $i\times(a-i)$ region, making a total of $i(a-i+1)$ valid bottom-left corners.

Thus, the total number of quadrilaterals that can be formed with its top-right corner in the $i$ -th column where $1\leqslant i\leqslant a-1$ is $i(a-i+1)^2$ ,

For $i=a$ , things are a little bit different. If we choose the only triangle in this column as the quadrilateral's top right corner, its valid bottom-left corners consist of the internal squares of the bottom slope grid and we get napkin-like trapeziums. In this case, for $i=a$ , the number of valid bottom-left corners is $\frac{a(a-1)}{2}$ . Since the right arrow grid is symmetric, we can do the same thing with the sides switched (top slope grid and bottom slope grid swapped). We get the same set of napkin trapeziums but mirrored. The total number of napkin trapeziums is $2\times\frac{a(a-1)}{2}=a(a-1)$ .

Thus the total number of crossover quadrilaterals is $\begin{aligned}\displaystyle\left[\sum_{i=1}^{a-1}i(a-i+1)^2\right]+a(a-1)&=\left\{\sum_{i=1}^ai[(a+1)^2-2(a+1)i+i^2]\right\}+a(a-1) \\ &=\left\{\sum_{i=1}^{a-1}[(a+1)^2i-2(a+1)i^2+i^3]\right\}+a(a-1) \\ &=\frac{a(a-1)(a+1)^2}{2}-\frac{a(a-1)(a+1)(2a-1)}{3}+\left[\frac{a(a-1)}{2}\right]^2+a(a-1) \\ &=a(a-1)\left[\frac{(a+1)^2}{2}-\frac{(a+1)(2a-1)}{3}+\frac{a(a-1)}{4}+1\right] \\ &=\frac{a(a-1)}{12}[6a^2+12a+6-4(2a^2+a-1)+3a^2-3a+12] \\ &=\frac{a(a-1)(a^2+5a+22)}{12} \end{aligned}$

Therefore, the total number of quadrilaterals in an $a$ -tiered right arrow grid is $\begin{aligned}\frac{a(a-1)(a+1)(a+10)}{12}+\frac{a(a-1)(a^2+5a+22)}{12}&=\frac{a(a-1)(2a^2+16a+32)}{12} \\ &=\frac{a(a-1)(a^2+8a+16)}{6} \\ &=\frac{a(a-1)(a+4)^2}{6} \end{aligned}$

Now, substituting $a=30$ , we would get the answer $167620$ .

Here is my solution.

First, I draw all 12 solutions for $a = 2$

Second, I tried to find an incremental path for $a = 3$

Eventually, it came out that all $a=2$ solutions touching the base (which are all of them but that will not be the case for $a>2$ ), can be stretched to $a=3$ solution. (Let's call this set of solutions $A_{1}$ )

$A_{1} = number \space of \space solutions \space touching \space the \space base$

We can also stretch triangles (which are not $a=2$ solutions) to get another set of $a=3$ solutions. (We will call this set $B$ )

$B=2(a-1)+2=2a$

And rest of the $a=3$ solutions lie on the left side of the red line (Call this set $C$ )

$C =\frac{(2a-2)(2a-1)}{2}+ 2(2a-2)+1=\frac{(2a-2)(2a+3)}{2}+1$

Finally, the update equations are as follows:

$A_{1}=C+B+A_{1(a-1)}$

$Total=Total_{(a-1)} +A_{1}$

This is how I calculated it: $\displaystyle\sum_{n=1}^{29} \left(n(30-n)(61-2n)+2n(60-2n)+2n(30-n)+n+2n\right)=167620$

After complex operations

F(a)=2F(a-1)-F(a-2)+4(a-1)+a(2a-1)+2