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)) -&gt; 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) -&gt; i32 {
    while y != 0 {
        let z = x % y;
        x = y;
        y = z;
    }
    x
}

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

fn main() {
    for &amp;n in &amp;[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 100] {
        let sides = [
            (1..n).map(|i| (i, 0)).collect::&lt;Vec&lt;_&gt;&gt;(),
            (1..n).map(|i| (n - i, i)).collect::&lt;Vec&lt;_&gt;&gt;(),
            (1..n).map(|i| (0, n - i)).collect::&lt;Vec&lt;_&gt;&gt;(),
        ];
        let segments = (0..)
            .zip(&amp;sides)
            .flat_map(|(i, side0)| {
                sides[i + 1..].iter().flat_map(move |side1| {
                    side0
                        .iter()
                        .flat_map(move |&amp;a| side1.iter().map(move |&amp;b| (a, b)))
                })
            })
            .collect::&lt;Vec&lt;_&gt;&gt;();
        let mut regions = 1 + segments.len() as i64;
        let mut intersections = HashMap::new();
        for (i, &amp;(a, b)) in (0..).zip(&amp;segments) {
            for &amp;(c, d) in &amp;segments[i + 1..] {
                let p = det(c, d, a);
                let q = det(c, d, b);
                if p * q &lt; 0 &amp;&amp; det(a, b, c) * det(a, b, d) &lt; 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 answer is simple $100^3$. Discard the amount of parts that disappear when three segment get through the same point, At least $99^3$. I assume that you know how to find all other such cases (if exist:))