Find how many parts are in a triangle

geometrytriangles

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?

Best Answer

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

Related Question