Find how many parts are in a triangle

Recently, I got this interesting riddle in a math test, which I still can't solve. Here are the exact words:

Each side of an equilateral triangle was divided into 100 equal parts. Points received connected by segments. How many parts did you get?

Here is an example for a triangle with just 3 points on each side:

That much lines really confuses me. I tried to find a ratio between number of lines and parts, and how does each new line drawn divides the others, but it doesn't seem to work. What could be the possible solution to this?


This Rust program gives the answer 205689153 in about a minute and a half. It’s based on the Euler characteristic formula $V - E + F = 1$ for a connected plane graph with $V$ vertices, $E$ edges, and $F$ faces. But there doesn’t seem to be a nice formula to find $V$ and $E$ without lots of computation, because in some cases, multiple pairs of segments concur at the same intersection point. So we just list all the intersections and count up the duplicates.

use std::collections::hash_map::HashMap;

fn det(a: (i32, i32), b: (i32, i32), c: (i32, i32)) -> i32 {
    (b.0 - a.0) * (c.1 - a.1) - (b.1 - a.1) * (c.0 - a.0)
}

fn gcd(mut x: i32, mut y: i32) -> i32 {
    while y != 0 {
        let z = x % y;
        x = y;
        y = z;
    }
    x
}

fn reduce(n: i32, d: i32) -> (i32, i32) {
    let g = gcd(n, d);
    (n / g, d / g)
}

fn main() {
    for &n in &[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 100] {
        let sides = [
            (1..n).map(|i| (i, 0)).collect::<Vec<_>>(),
            (1..n).map(|i| (n - i, i)).collect::<Vec<_>>(),
            (1..n).map(|i| (0, n - i)).collect::<Vec<_>>(),
        ];
        let segments = (0..)
            .zip(&sides)
            .flat_map(|(i, side0)| {
                sides[i + 1..].iter().flat_map(move |side1| {
                    side0
                        .iter()
                        .flat_map(move |&a| side1.iter().map(move |&b| (a, b)))
                })
            })
            .collect::<Vec<_>>();
        let mut regions = 1 + segments.len() as i64;
        let mut intersections = HashMap::new();
        for (i, &(a, b)) in (0..).zip(&segments) {
            for &(c, d) in &segments[i + 1..] {
                let p = det(c, d, a);
                let q = det(c, d, b);
                if p * q < 0 && det(a, b, c) * det(a, b, d) < 0 {
                    if *intersections
                        .entry((
                            reduce(a.0 * q - b.0 * p, q - p),
                            reduce(a.1 * q - b.1 * p, q - p),
                        ))
                        .or_insert(i)
                        == i
                    {
                        regions += 1;
                    }
                }
            }
        }
        println!("{} {}", n, regions);
    }
}

Output:

1 1
2 4
3 27
4 130
5 385
6 1044
7 2005
8 4060
9 6831
10 11272
100 205689153

Here are the results when dividing each side into $n$ parts for all $1 \le n \le 120$:

1, 4, 27, 130, 385, 1044, 2005, 4060, 6831, 11272, 16819, 26436, 35737, 52147, 69984, 92080, 117952, 157770, 193465, 249219, 302670, 368506, 443026, 546462, 635125, 757978, 890133, 1041775, 1191442, 1407324, 1581058, 1837417, 2085096, 2365657, 2670429, 3018822, 3328351, 3771595, 4213602, 4694337, 5140756, 5769306, 6279934, 6987991, 7661637, 8355580, 9122179, 10077408, 10860478, 11882437, 12859392, 13960045, 15028393, 16394970, 17583472, 18980292, 20342943, 21871402, 23445913, 25385163, 26876233, 28911262, 30947106, 32961190, 35048842, 37459587, 39569107, 42324415, 44890158, 47731083, 50294455, 53649654, 56360842, 59879101, 63420084, 66857380, 70408212, 74445273, 78040573, 82622160, 86647137, 91124683, 95665744, 101133132, 105569497, 110811364, 116310795, 122023012, 127352503, 134068833, 139524337, 146093875, 152642448, 159496621, 166630228, 174340821, 180991705, 189418792, 197333184, 205689153, 213416806, 223144743, 231395536, 241509546, 251118018, 260392267, 270368527, 282027867, 291604741, 303685314, 314632365, 326674581, 337687342, 351301695, 363291763, 376664530, 390047007, 403508989, 417603979, 433264083


The problem as quoted seems not quite clear, but assuming that the aim is to count the number of segments joining every point of division on the sides of the triangle (excluding vertices) with every point (including vertices) not already joined with it by a straight line, then as @Roddy MacPhee notes, there are $36$ segments when each side of the triangle is divided into four parts. Somewhat easier to count, as in the figure below, there are $18$ segments when each side is divided into three parts.

number of segments in equilateral triangle

If $n$ denotes the number of parts into which each side of the triangle is divided, I find that for $n=1, 2, 3, 4, 5, 6$ the number of segments joining points is $0, 6, 18, 36, 60, 90$, respectively.

And from this it can be seen that, if $N$ denotes the number of segments, then$$N=3(n^2-n)$$

Hence, if each side is divided into $100$ parts$$N=3(100^2-100)=29,700$$

Revised answer

In light of OP's clarifying comment, that the question seeks the number of regions (bounded areas), not line segments, and in agreement with the comment of @JaapSherphuis, and OP's figure, that no segments are drawn from the vertices of the equilateral triangle, I must revise my answer as follows.

1) A line joining two points on adjacent sides of the equilateral triangle adds one region to the triangle's interior if it crosses no line in between.

2) If it crosses one line it adds two regions; if two lines three regions, and so on.

3) But when it crosses two or more concurrent lines it adds only one region for that crossing, i.e. as if it were crossing only one line.

Using GeoGebra, I counted regions up to $n=6$, i.e. for equilateral triangles with sides divided into 2, 3, 4, 5, and 6 equal parts. But since counting regions quickly becomes difficult with increasing $n$, I found it best to begin with an empty triangle, draw the lines one by one in a systematic way, and count for each new line the number of lines crossed, adding $1$ to get the number of new regions produced by that line. Because of symmetry, it helps to draw the three segments of each triad one after another, a triad being three lines which coincide when the triangle is rotated thru $120^o$. If the lines do not cross one another, the number of regions added by each is the same; and if they do cross, the second adds one more region than the first, and the third one more than the second. This helps in detecting miscounts. Finally, I kept track whenever the number of new regions is reduced because the line crosses two or more lines at their intersection. This happens more and more with increasing $n$, and makes the problem that much more difficult, as @JaapScherphuis also notes.

For $n=1, 2, 3, 4, 5, 6$, then, I count $$1, 4, 27, 130, 385, 1038$$ regions in the triangle. I have not been able to find the law of these numbers, which are exact since they take account of the deductions for concurrencies. But if we disregard the concurrencies, i.e. consider only the number of lines crossed by each successive line, we get instead$$1, 4, 28, 136, 445, 1126$$

And these numbers are given by the expression$$\frac{3m^2}{4}(3m^2-4m+5)+1$$where $m=n-1$.

The numbers $3-4-5$ are reminiscent of the basic Pythagorean right triangle, and it is intriguing to see them appear here in connection with the equilateral triangle. On the other hand, it seems the expression applies just as well to equilateral triangles whose sides are divided into $n$ parts unequal to one another. The concurrencies, their number and pattern, are determined by the condition that the sides of the triangle are divided into $n$ equal parts. So my solution seems more general in nature.

But while the above expression does not provide a means for computing exactly the number of regions sought, it does seem to give an upper bound. I am unsure how far off this approximation will be in the posted case, since concurrencies are fairly numerous even for relatively small $n$. In the figure below, for example, where $n=5$, the unlettered interior points mark forty-two 3-line concurrencies, each reducing by $1$ the count of new regions for the third line crossing at that point. $P,Q,R$ are three 5-line concurrencies, each reducing the count of new regions by $6$. For when the third line crosses at $P$, $1$ new region is subtracted from the count for that line, when the fourth line crosses, $2$ are subtracted, and when the fifth line crosses, $3$, giving $1+2+3=6$ for point $P$, and the same for $Q$ and $R$. Thus as noted above, there are $42+18=60$ fewer regions than my expression gives for $n=5$, i.e. $385$ instead of $445$.

regions when n=5

The best answer I can make, then, to the posted question, is that for $n=100$ there are somewhat fewer than$$\frac{3\cdot 99^2}{4}(3\cdot 99^2-4\cdot 99+5)+1=213,259,960$$regions in the equilateral triangle.


I'll take it you want number of regions created. This is tedious to count them all, until you realize there's symmetry. Breaking the triangle into 4 equilateral triangles, 3 are just rotations of each other there are 26 in each of these for 78 in those triangles. You can do this again with the last triangle, giving 14 regions in each of 3 subtriangles. Lastly, you'll note that the remaining triangle has 10 regions. so you have $3(26+14)+10= 130$ regions. okay slight error possibly in counting in each triangle. still gives you a way to figure it out.