Project Euler

Cross-hatched Triangles

Consider an equilateral triangle of side length n subdivided by a triangular grid (lines parallel to each side at unit spacing) and further cross-hatched by lines from each vertex through equally-s...

Source sync Apr 19, 2026

Problem #0163

Level Level 10

Solved By 2,170

Languages C++, Python

Answer 343047

Length 579 words

geometrylinear_algebragraph

Consider an equilateral triangle in which straight lines are drawn from each vertex to the middle of the opposite side, such as in the size $1$ triangle in the sketch below.

Sixteen triangles of either different shape or size or orientation or location can now be observed in that triangle. Using size $1$ triangles as building blocks, larger triangles can be formed, such as the size $2$ triangle in the above sketch. One-hundred and four triangles of either different shape or size or orientation or location can now be observed in that size $2$ triangle.

It can be observed that the size $2$ triangle contains $4$ size $1$ triangle building blocks. A size $3$ triangle would contain $9$ size $1$ triangle building blocks and a size $n$ triangle would thus contain $n^2$ size $1$ triangle building blocks.

If we denote $T(n)$ as the number of triangles present in a triangle of size $n$, then \begin {align*} T(1) &= 16\\ T(2) &= 104 \end {align*}

Find $T(36)$.

Problem 163: Cross-hatched Triangles

Definitions

Definition 1. A cross-hatched equilateral triangle of size $n$ is the figure obtained by overlaying 6 families of lines on an equilateral triangle with side length $n$ .

Definition 2. In oblique coordinates $(u, v)$ where the main triangle has vertices $(0,0)$ , $(n,0)$ , $(0,n)$ and interior $\{(u,v) : u \geq 0,\; v \geq 0,\; u + v \leq n\}$ , a line $\ell$ is specified by an equation $au + bv = c$ with integer coefficients.

Mathematical Development

Theorem 1 (Line families). The 6 line families in the cross-hatched triangle of size $n$ are:

Family	Equation	Direction $(a,b)$	Parameter range
$F_1$	$u = k$	$(1, 0)$	$k = 0, 1, \ldots, n$
$F_2$	$v = k$	$(0, 1)$	$k = 0, 1, \ldots, n$
$F_3$	$u + v = k$	$(1, 1)$	$k = 0, 1, \ldots, n$
$F_4$	$u - v = k$	$(1, -1)$	$k = -(n-1), \ldots, n-1$
$F_5$	$u + 2v = k$	$(1, 2)$	$k = 1, \ldots, 2n-1$
$F_6$	$2u + v = k$	$(2, 1)$	$k = 1, \ldots, 2n-1$

All six direction vectors are pairwise non-parallel.

Proof. Families $F_1$ — $F_3$ are the standard triangular grid at unit spacing. Families $F_4$ — $F_6$ arise from the cross-hatching: the medians and their translates from each vertex to the midpoints of segments on the opposite side. The direction vectors $(1,0)$ , $(0,1)$ , $(1,1)$ , $(1,-1)$ , $(1,2)$ , $(2,1)$ are pairwise non-parallel (no pair is a scalar multiple of the other), which can be verified by checking that all $\binom{6}{2} = 15$ cross-products $a_i b_j - a_j b_i$ are nonzero. $\square$

Theorem 2 (Triangle formation criterion). Three lines $\ell_1, \ell_2, \ell_3$ from three distinct families form a non-degenerate triangle if and only if:

The three families have pairwise distinct directions (guaranteed since all 6 directions are distinct).
The three lines are not concurrent.
All three pairwise intersection points lie within or on the boundary of the main triangle.

Proof. Two lines from the same family are parallel and cannot form a triangle edge. Three lines from three distinct non-parallel families intersect pairwise in three points, forming a triangle if and only if the three points are distinct (equivalently, the lines are not concurrent). The triangle is valid only if it lies within the main figure, which requires all three vertices to satisfy $u \geq 0$ , $v \geq 0$ , $u + v \leq n$ . $\square$

Lemma 1 (Rational intersection). The intersection of line $a_1 u + b_1 v = c_1$ from family $F_i$ and line $a_2 u + b_2 v = c_2$ from family $F_j$ ( $i \neq j$ ) is the point:

u = \frac{c_1 b_2 - c_2 b_1}{a_1 b_2 - a_2 b_1}, \qquad v = \frac{a_1 c_2 - a_2 c_1}{a_1 b_2 - a_2 b_1}.

All quantities are integers, and the denominator $D = a_1 b_2 - a_2 b_1 \neq 0$ .

Proof. By Cramer’s rule applied to the $2 \times 2$ system. The determinant is nonzero since the directions are non-parallel. $\square$

Lemma 2 (Containment test). A point $(p/d, q/d)$ with $d > 0$ lies in the closed main triangle if and only if $p \geq 0$ , $q \geq 0$ , and $p + q \leq nd$ .

Proof. Substituting into the inequalities $u \geq 0$ , $v \geq 0$ , $u + v \leq n$ and clearing the positive denominator. $\square$

Lemma 3 (Concurrency test). Three lines are concurrent if and only if the intersection of the first two equals the intersection of the first and third. In rational coordinates $(p_1/d_1, q_1/d_1)$ and $(p_2/d_2, q_2/d_2)$ , this is $p_1 d_2 = p_2 d_1$ and $q_1 d_2 = q_2 d_1$ .

Proof. Direct from the uniqueness of intersection points in distinct directions. $\square$

Editorial

Count triangles in a cross-hatched equilateral triangle of size n = 36. Six line families in oblique coordinates (u, v) with triangle u >= 0, v >= 0, u + v <= n. A triangle is formed by choosing one line from each of three distinct families; we check containment and non-concurrency via exact rational arithmetic.

Pseudocode

    total = 0
    families = [(1,0), (0,1), (1,1), (1,-1), (1,2), (2,1)]
    ranges = [0..n, 0..n, 0..n, -(n-1)..n-1, 1..2n-1, 1..2n-1]

    for each triple (i, j, k) with 0 <= i < j < k <= 5:
        (a1,b1), (a2,b2), (a3,b3) = families[i], families[j], families[k]
        D12 = a1*b2 - a2*b1; D13 = a1*b3 - a3*b1; D23 = a2*b3 - a3*b2
        if any D == 0: skip // parallel pair (does not occur)
        For each c1 in ranges[i]:
            For each c2 in ranges[j]:
                P12 = intersect(a1,b1,c1, a2,b2,c2)
                If P12 outside triangle then continue
                For each c3 in ranges[k]:
                    P13 = intersect(a1,b1,c1, a3,b3,c3)
                    If P13 outside triangle then continue
                    P23 = intersect(a2,b2,c2, a3,b3,c3)
                    If P23 outside triangle then continue
                    if P12 == P13: continue // concurrent
                    total += 1
    Return total

Complexity Analysis

Time. There are $\binom{6}{3} = 20$ family triples. For each triple, the three nested loops iterate over $O(n)$ lines each, giving $O(n^3)$ intersection tests per triple. Total: $O(20 \cdot n^3)$ . For $n = 36$ : approximately $20 \cdot 37^3 \approx 10^6$ tests.

Space. $O(n)$ for line parameter storage, $O(1)$ working space per test.

Answer

\boxed{343047}

C++ project_euler/problem_163/solution.cpp

#include <bits/stdc++.h>
using namespace std;

/*
 * Project Euler Problem 163: Cross-hatched Triangles
 *
 * Count triangles in a cross-hatched equilateral triangle of size n = 36.
 * Six line families in oblique coordinates; enumerate all C(6,3) = 20
 * family triples and all line triples, checking containment and
 * non-concurrency via exact integer arithmetic.
 */

int main() {
    const int n = 36;

    int a[6] = {1, 0, 1, 1, 1, 2};
    int b[6] = {0, 1, 1, -1, 2, 1};

    vector<vector<int>> lines(6);
    for (int k = 0; k <= n; k++) lines[0].push_back(k);
    for (int k = 0; k <= n; k++) lines[1].push_back(k);
    for (int k = 0; k <= n; k++) lines[2].push_back(k);
    for (int k = -(n - 1); k <= n - 1; k++) lines[3].push_back(k);
    for (int k = 1; k <= 2 * n - 1; k++) lines[4].push_back(k);
    for (int k = 1; k <= 2 * n - 1; k++) lines[5].push_back(k);

    long long total = 0;

    for (int f1 = 0; f1 < 6; f1++) {
        for (int f2 = f1 + 1; f2 < 6; f2++) {
            for (int f3 = f2 + 1; f3 < 6; f3++) {
                int a1 = a[f1], b1 = b[f1];
                int a2 = a[f2], b2 = b[f2];
                int a3 = a[f3], b3 = b[f3];

                int d12 = a1 * b2 - a2 * b1;
                int d13 = a1 * b3 - a3 * b1;
                int d23 = a2 * b3 - a3 * b2;
                if (d12 == 0 || d13 == 0 || d23 == 0) continue;

                for (int c1 : lines[f1]) {
                    for (int c2 : lines[f2]) {
                        long long nu12 = (long long)c1 * b2 - (long long)c2 * b1;
                        long long nv12 = (long long)a1 * c2 - (long long)a2 * c1;
                        long long dd12 = d12;
                        if (dd12 < 0) { nu12 = -nu12; nv12 = -nv12; dd12 = -dd12; }
                        if (nu12 < 0 || nv12 < 0 || nu12 + nv12 > (long long)n * dd12)
                            continue;

                        for (int c3 : lines[f3]) {
                            long long nu13 = (long long)c1 * b3 - (long long)c3 * b1;
                            long long nv13 = (long long)a1 * c3 - (long long)a3 * c1;
                            long long dd13 = d13;
                            if (dd13 < 0) { nu13 = -nu13; nv13 = -nv13; dd13 = -dd13; }
                            if (nu13 < 0 || nv13 < 0 || nu13 + nv13 > (long long)n * dd13)
                                continue;

                            long long nu23 = (long long)c2 * b3 - (long long)c3 * b2;
                            long long nv23 = (long long)a2 * c3 - (long long)a3 * c2;
                            long long dd23 = d23;
                            if (dd23 < 0) { nu23 = -nu23; nv23 = -nv23; dd23 = -dd23; }
                            if (nu23 < 0 || nv23 < 0 || nu23 + nv23 > (long long)n * dd23)
                                continue;

                            // Non-concurrency: P12 != P13
                            if (nu12 * dd13 == nu13 * dd12 && nv12 * dd13 == nv13 * dd12)
                                continue;

                            total++;
                        }
                    }
                }
            }
        }
    }

    cout << total << endl;
    return 0;
}

Python project_euler/problem_163/solution.py

"""
Project Euler Problem 163: Cross-hatched Triangles

Count triangles in a cross-hatched equilateral triangle of size n = 36.

Six line families in oblique coordinates (u, v) with triangle
u >= 0, v >= 0, u + v <= n.  A triangle is formed by choosing one line
from each of three distinct families; we check containment and
non-concurrency via exact rational arithmetic.
"""


def solve():
    n = 36

    families = [(1, 0), (0, 1), (1, 1), (1, -1), (1, 2), (2, 1)]
    line_ranges = [
        list(range(0, n + 1)),
        list(range(0, n + 1)),
        list(range(0, n + 1)),
        list(range(-(n - 1), n)),
        list(range(1, 2 * n)),
        list(range(1, 2 * n)),
    ]

    def intersect(a1, b1, c1, a2, b2, c2):
        det = a1 * b2 - a2 * b1
        if det == 0:
            return None
        nu = c1 * b2 - c2 * b1
        nv = a1 * c2 - a2 * c1
        d = det
        if d < 0:
            nu, nv, d = -nu, -nv, -d
        return (nu, nv, d)

    def inside(nu, nv, d):
        return nu >= 0 and nv >= 0 and nu + nv <= n * d

    total = 0
    for f1 in range(6):
        a1, b1 = families[f1]
        for f2 in range(f1 + 1, 6):
            a2, b2 = families[f2]
            for f3 in range(f2 + 1, 6):
                a3, b3 = families[f3]
                for c1 in line_ranges[f1]:
                    for c2 in line_ranges[f2]:
                        p12 = intersect(a1, b1, c1, a2, b2, c2)
                        if p12 is None or not inside(*p12):
                            continue
                        for c3 in line_ranges[f3]:
                            p13 = intersect(a1, b1, c1, a3, b3, c3)
                            if p13 is None or not inside(*p13):
                                continue
                            p23 = intersect(a2, b2, c2, a3, b3, c3)
                            if p23 is None or not inside(*p23):
                                continue
                            nu1, nv1, d1 = p12
                            nu2, nv2, d2 = p13
                            if nu1 * d2 == nu2 * d1 and nv1 * d2 == nv2 * d1:
                                continue
                            total += 1

    print(total)


solve()