Triangles Containing the Origin

Consider the set $I_r$ of points $(x,y)$ with integer co-ordinates in the interior of the circle with radius $r$, centered at the origin, i.e. $x^2 + y^2 \lt r^2$.
For a radius of $2$, $I_2$ contains the nine points $(0,0)$, $(1,0)$, $(1,1)$, $(0,1)$, $(-1,1)$, $(-1,0)$, $(-1,-1)$, $(0,-1)$ and $(1,-1)$. There are eight triangles having all three vertices in $I_2$ which contain the origin in the interior. Two of them are shown below, the others are obtained from these by rotation.

For a radius of $3$, there are $360$ triangles containing the origin in the interior and having all vertices in $I_3$ and for $I_5$ the number is $10600$.
How many triangles are there containing the origin in the interior and having all three vertices in $I_{105}$?

Let’s understand the problem with a geometrical point of view. Note that the number of lattice points (points with integer coordinates) that lie strictly inside a circle centered at the origin with radius $r$ is approximately proportional to the area of the circle, i.e., $\pi r^2$ for large $r$. However, we need to correct this approximation by subtracting the number of points that lie on the four axes, i.e., $4r$ because it’s overestimated. Therefore, the number of lattice points inside the circle without touching its boundary (the sides of the circle) is around $\pi r^2-4r$.

We consider the circle of radius $r$ purely as the boundary here. So no points are considered on this boundary. Only the area enclosed by the boundary is taken into account.

Now, we have to count the triangles formed by using these lattice points as vertices. The number of such triangles can be counted by selecting any three points from the available lattice points, i.e.,

$\binom{n}{3}$ = n(n-1)(n-2)/6

where n is the total number of lattice points we have.

We require that the origin lies in the interior of the triangle. This condition is challenging to directly count. Hence, we will count its complement – the number of triangles that do not contain the origin in their interior.

The origin will not lie in the interior of the triangle formed by the points $(x_1, y_1)$, $(x_2,y_2)$ and $(x_3, y_3)$ if and only if these three points are collinear or they lie in the same quadrant or on the same axis. The number of collinear triplets is small and can be neglected in front of the total number of triplets. The other case is easier to count.

There are roughly $\pi r^2/4 – r$ points in each quadrant and $r$ points on each axis for large $r$. Therefore, the number of bad triplets, i.e., the triangles that do not contain the origin, is

$4*\binom{\pi r^2/4 – r}{3} + 4 * \binom{r}{3} \approx \pi^3 r^6/96 – \pi^2 r^5/8 + \pi r^4/6$.

The total number of triangles is $\binom{\pi r^2 – 4r}{3} \approx \pi^3 r^6/6 – \pi^2 r^5 + \pi r^4/2$.

The number of good triangles is obtained by subtracting the number of bad triangles from the total triangles. Hence the number of good triangles,

$T = \pi^3 r^6/6 – \pi^2 r^5 + \pi r^4/2 – (\pi^3 r^6/96 – \pi^2 r^5/8 + \pi r^4/6)$.

Simplifying, you have:

$T \approx 17/96 * \pi^3 r^6$.

Substituting $r = 105$, we get

$T \approx 17/96 * \pi^3 * 105^6$

which, after rounding to the nearest integer, gives about

$T \approx 67564224$.

So, there are approximately 67564224 triangles in $I_{105}$. Please note that this is an approximation because it’s include real-valued co-ordinates. The exact value could be slightly different if a full count which only considers integer co-ordinate sets was done.

More Answers: