3
$\begingroup$

For an equilateral triangle of side length $n$ dots, as shown in this diagram below, construct a function, $f(n)$, which outputs the number of lines needed to connect up every dot to every other dot. A straight line through three or more dots counts as only one line! E.g. $f(3) = 9$ and $f(4) = 24$.

diagram

Can anyone point me in the right direction with this problem? Perhaps tell me what area of mathematics or what concepts would help me solve this? If this is a trivial problem don't give the answer but tell let me know. Thanks.

$\endgroup$
4
  • 1
    $\begingroup$ Hmm... how would $f(3)=9$? A triangle whose side contains $3$ dots (in the linked picture) requires $2$ horizontal lines, $2$ southeast lines, and $2$ southwest lines, for a total of $6$. Perhaps clarify what you mean by "connect up all the dots to one another." $\endgroup$ Jun 26 '18 at 19:22
  • $\begingroup$ Every dot is connected to every other dot via a straight line. $\endgroup$
    – ThoughtBox
    Jun 26 '18 at 19:31
  • $\begingroup$ @Frpzzd plus the three lines connecting the corner points to the middle point of the opposite side. $\endgroup$
    – Joffan
    Jun 26 '18 at 19:42
  • $\begingroup$ Are you sure $f(4)$ is not $21$? Or are there dots not along the edge for $n>3$? Can you clarify what the shape should be for $n=4$ and possibly $n=5$? $\endgroup$
    – Alex Jones
    Jun 26 '18 at 19:45
2
$\begingroup$

For a side of $m$ dots there are a total of $n=\frac 12m(m+1)$ dots. There are then $\frac 12n(n-1)$ pairs of dots. If you have a line with $k \gt 2$ dots on it, it accounts for $\frac 12k(k-1)$ of the pairs of dots, so it reduces the count by $\frac 12k(k-1)-1$

We can see this for the order $4$ triangle. There are $10$ points, three lines with four points (the sides) and three lines with three points. The number of lines is then $\frac 12\cdot 10 \cdot 9 - 3(\frac 12\cdot 4 \cdot 3-1)-3(\frac 12 \cdot 3 \cdot 2 -1)=45-3\cdot 5 -3 \cdot 2=24$

If we do the order $5$ triangle we have $15$ dots, three lines with five dots, three with four dots, and six with three dots. The new ones with three dots run from a corner through the center to the middle of the other side. This gives $\frac 12\cdot 15\cdot 14-3\cdot 9-3\cdot 5 -6\cdot 2=51$ lines

This gives sequence A244504 which begins $$3, 9, 24, 51, 102, 177, 294, 459, 690, 987, 1380, 1875, 2508, 3279, 4212, 5319, 6648, 8199, 10026, 12141, 14580, 17343, 20496, 24051, 28068, 32547, 37542, 43071, 49218, 55983, 63456, 71661, 80658, 90447, 101100, 112635, 125160, 138675, 153252, 168915, 185784$$

No closed formula is given.

$\endgroup$
2
  • $\begingroup$ I understand your logic but I asked for a formula not a sequence nor a summation (as is provided in the description of the OEIS link). Can a "closed" formula be given? $\endgroup$
    – ThoughtBox
    Jun 26 '18 at 20:08
  • 2
    $\begingroup$ Your request seemed much more open ended that that. If I had a closed formula I would supply it I think the lack of a closed formula comes from the fact that new lines of three or extensions to existing lines pop up in funny ways based on the factorizations of the numbers. $\endgroup$ Jun 26 '18 at 20:36
1
$\begingroup$

Here's a solution for the problem described, i.e. if the shape is an equilateral triangle whose sides are $n$ equally spaced dots. This is assuming the dots along the sides of the triangle are the only dots.

First, count the number of dots. There are $n$ dots along one edge, with one of those dots being shared with the other two edged. Then, there are $n-1$ new dots along a second edge, with one of those shared with the final edge. Finally, there are $n-2$ dots remaining on the third edge. This gives a total of $n+(n-1)+(n-2) = 3(n-1)$ dots.

The number of edges connecting two dots is then $\binom{3(n-1)}{2} = \frac{3(n-1)(3n-4)}{2}$. However, along each side of the triangle, there are $\binom{n}{2} = \frac{n(n-1)}{2}$ edges along the same line. So, we need to subtract all but one of these (the edge connecting the corners) for each side, totaling $3[\binom{n}{2}-1] = \frac{3(n+1)(n-2)}{2}$.

Thus, the total number of necessary lines is $$ f(n) = \binom{3(n-1)}{2}-3\left[\binom{n}{2}-1\right] = 3(n^2-3n+3) $$

This gives $f(2) = 3, f(3) = 9, f(4) = 21, f(5) = 39$ and so on.

$\endgroup$
10
  • 2
    $\begingroup$ The count of $24$ for the triangle of side $4$ indicates that OP is considering a filled triangle. $\endgroup$ Jun 26 '18 at 20:51
  • $\begingroup$ I had no indication of where OP got that answer from, and the question as described leaves it to the imagination. Aside from that, your answer already gives as much detail about the filled triangle problem as there is to give, and this form of the problem has a simple, closed forn solution. $\endgroup$
    – Alex Jones
    Jun 26 '18 at 20:59
  • $\begingroup$ @AlexanderJ93 I'll show you $\endgroup$
    – ray lin
    Jun 26 '18 at 21:01
  • 1
    $\begingroup$ @ThoughtBox I did ask for clarification but got none, however I answered the question as you described it. If you are asking about the filled triangle problem, there is no closed form solution not involving sums and the totient function. This is determined. $\endgroup$
    – Alex Jones
    Jun 26 '18 at 21:34
  • 1
    $\begingroup$ What does determined mean? And what makes you think that summation is unavoidable? $\endgroup$
    – ThoughtBox
    Jun 26 '18 at 21:35

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.