10
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ This is a case of dividing the side into 4 parts. And the number of parts is $4^3$ which is 64. $\endgroup$ – Moti Dec 31 '19 at 5:01
  • $\begingroup$ This is a case of dividing the side into 4 parts. And the number of parts is $4^3$ which is 64, Subtract 6. $\endgroup$ – Moti Dec 31 '19 at 5:11
  • $\begingroup$ @moti there's only 36 connecting all the points thst aren't vertices of the triangle in the example, try again. $\endgroup$ – user645636 Jan 1 at 12:35
  • $\begingroup$ 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? $\endgroup$ – Jaap Scherphuis Jan 2 at 10:19
  • $\begingroup$ @JaapScherphuis Number of regions. $\endgroup$ – Ver Nick Jan 2 at 11:04
3
+150
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you very much. That makes sense. $\endgroup$ – Ver Nick Jan 2 at 11:06
  • 2
    $\begingroup$ 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. $\endgroup$ – Jaap Scherphuis Jan 2 at 11:58
  • 1
    $\begingroup$ @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. $\endgroup$ – Edward Porcella Jan 3 at 21:15
  • $\begingroup$ I more just did 9 choose 2 =36 for the lines connecting the 3 points on each of 3 sides connected. $\endgroup$ – user645636 Jan 15 at 2:09
  • $\begingroup$ Thank you a lot! This explanation is really clear for beginners. $\endgroup$ – Ver Nick Jan 28 at 18:49
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you very much for your efforts in that task. I will award a bounty to this too as soon as I can. $\endgroup$ – Ver Nick Jan 29 at 8:09
  • $\begingroup$ 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. $\endgroup$ – Edward Porcella Jan 30 at 23:19
  • 1
    $\begingroup$ @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. $\endgroup$ – Anders Kaseorg Jan 31 at 2:41
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I'll confess I may know where you got this problem ... $\endgroup$ – user645636 Jan 28 at 9:53
  • $\begingroup$ 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 ... ) $\endgroup$ – user645636 Jan 28 at 11:52
-5
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Do a quick sanity check in the given figure above. There are clearly more than $3^3=27$ pieces in there. $\endgroup$ – Sam Dec 31 '19 at 5:44
  • $\begingroup$ I said between $100^3$ to $99^3$ $\endgroup$ – Moti Jan 1 at 6:41
  • $\begingroup$ 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.... $\endgroup$ – user645636 Jan 1 at 12:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.