Lattice Quadrilaterals

A simple quadrilateral is a polygon that has four distinct vertices, has no straight angles and does not self-intersect.
Let $Q(m, n)$ be the number of simple quadrilaterals whose vertices are lattice points with coordinates $(x,y)$ satisfying $0 \le x \le m$ and $0 \le y \le n$.
For example, $Q(2, 2) = 94$ as can be seen below:

It can also be verified that $Q(3, 7) = 39590$, $Q(12, 3) = 309000$ and $Q(123, 45) = 70542215894646$.
Find $Q(12345, 6789) \bmod 135707531$.

The problem at hand requires a combination of combinatorics and number theory to solve.

First, we have to figure out the combinatorics. In order to not have quadrilaterals that self-intersect, the points cannot simply be chosen in any order. Instead, we have to choose two points on the x axis and two on the y axis so that the quadrilaterals formed do not overlap.

This can be achieved by using the binomial coefficient or combination formula, denoted as “n choose k” or C(n,k), which gives the number of ways to choose k elements from a set of n elements.

In this case, the number of ways to choose 2 points from the x axis is C(m+1,2) and the number of ways to choose 2 points from the y is C(n+1,2). Therefore, the total number of unique quadrilaterals is C(m+1,2) * C(n+1,2).

But, there’s a problem here. The polygon could still be non-simple if both diagonals are vertical or horizontal lines. To prevent this, subtract out cases where all 4 points are on a line. This gives the equation C(m+1,2) * C(n+1,2) – (m+1) – (n+1).

Now, you have an expression for the number of simple quadrilaterals Q(m, n), but you are asked to find it modulo 135707531. One useful property of modular arithmetic is that operations like addition, subtraction, and multiplication can be performed ‘modularly.’ By using the properties, you can compute your answer modulo 135707531 at each step to keep the numbers manageable.

Finally, substitute the provided (m, n) values into your final expression and then reduce your answer modulo 135707531. It’s difficult to do exact numbers without computation but this gives you the process to solve the problem.

More Answers: