# 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 is a case of dividing the side into 4 parts. And the number of parts is $4^3$ which is 64.
– Moti
Dec 31, 2019 at 5:01
• This is a case of dividing the side into 4 parts. And the number of parts is $4^3$ which is 64, Subtract 6.
– Moti
Dec 31, 2019 at 5:11
• @moti there's only 36 connecting all the points thst aren't vertices of the triangle in the example, try again.
– user645636
Jan 1, 2020 at 12:35
• Is the question asking for the number of regions that the triangle is split into, or the number of line segments that the newly drawn lines are split into? Jan 2, 2020 at 10:19
• @JaapScherphuis Number of regions. Jan 2, 2020 at 11:04

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

• Thank you very much for your efforts in that task. I will award a bounty to this too as soon as I can. Jan 29, 2020 at 8:09
• You give values for $n=1-10$ and $n=100$. I don't know how to work the program you refer to, and would much appreciate it if you would give me the output for a few more values--say $n=11-20$? It may be a fool's errand on my part, but I still wonder about the law of the difference between the values given by my expression, which ignore concurrencies, and the true number of regions. Subtracting the "concurrency tax" (if the rule for calculating it is not too difficult) from the gross value given by my expression would give the true value. Jan 30, 2020 at 23:19
• @EdwardPorcella Sure, I’ve added the results for all $1 \le n \le 120$. I’m pretty convinced that there’s not a simple formula to be found, but you’re welcome to try. Jan 31, 2020 at 2:41
• Beautiful Rust code! The integer series is actually not part of the OEIS. I wonder if it should? (And, per extension, the same question for squares, regular pentagon, hexagon,....) I only stumbled across your post, because I recently did a small puzzle on that topic and couldn't find these sequences in the OEIS. Oct 25, 2020 at 20:06

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.

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$$

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$$.

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.

• Thank you very much. That makes sense. Jan 2, 2020 at 11:06
• You are also drawing lines through the vertices of the main triangle, which the OP does not have. There are $3(n-1)^2$ lines (3 ways to choose 2 sides of the triangle, $n-1$ choices of point on each side), whereas you counted $3(n-1)^2 + 3(n-1) = 3n(n-1)$ by including $n-1$ from each of the main triangle's vertices. The question however is about the number of regions that the triangle is split into, not the number of lines. Jan 2, 2020 at 11:58
• @JaapScherpuis--Yes, I was assuming that the figure was from OP, not the test giver, and that the question was not meant to be overly difficult. So I connected the vertices too and went from there, but you could leave them unconnected and still find a rule fairly easily--if we're counting lines, not areas. But the problem is obscurely formulated, don't you think? I take "points received" to mean "division points", but it seems needlessly misleading to mean "segments" in the first use of "parts" but "regions" or "areas" in the second. And as others note, it makes a much harder problem. Jan 3, 2020 at 21:15
• I more just did 9 choose 2 =36 for the lines connecting the 3 points on each of 3 sides connected.
– user645636
Jan 15, 2020 at 2:09
• Thank you a lot! This explanation is really clear for beginners. Jan 28, 2020 at 18:49

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.

• I'll confess I may know where you got this problem ...
– user645636
Jan 28, 2020 at 9:53
• I know it comes down to numbers of certain multi-intersections and the ceiling of n/2 ( 3 intersections are 6 above, 2 intersections are ... )
– user645636
Jan 28, 2020 at 11:52

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:))

• Do a quick sanity check in the given figure above. There are clearly more than $3^3=27$ pieces in there.
– Sam
Dec 31, 2019 at 5:44
• I said between $100^3$ to $99^3$
– Moti
Jan 1, 2020 at 6:41
• There's actually 36 line segments connecting all 9 points above prior to overlap elimination. plus the amount connecting vertices of the triangle... oh and any.insection....
– user645636
Jan 1, 2020 at 12:39