3
$\begingroup$

Suppose $A_1A_2 . . . A_{20}$ is a $20-$sided regular polygon.

How many non-isosceles (scalene) triangles can be formed whose vertices are among the vertices of the polygon but whose sides are not the sides of the polygon?

I could'nt find a cute answer to this problem. My answer is different from those at other websites. Not to mention that the answers are also different at different websites.

$\endgroup$
  • $\begingroup$ Can you give the websites on which there are answers ? $\endgroup$ – Jean Marie Nov 20 '16 at 10:43
  • $\begingroup$ Please provide your answer, as well as links to those "other websites". (The original source of the problem would be helpful, as well.) Otherwise, we could just be duplicating existing work, which is a waste of time and effort for everyone involved. $\endgroup$ – Blue Nov 21 '16 at 8:58
3
$\begingroup$

We first count all nondegenerate triangles containing no edge $A_iA_{i+1}$, and then subtract the isosceles triangles among these.

Put the first vertex $v_1$ at $A_0=A_{20}$. If you put $v_2$ at $A_2$ or $A_{18}$ then there are $15$ allowed $A_i$ left for $v_3$. If you put $v_2$ at an $A_i$ with $3\leq i\leq 17$ then there are $2\cdot 3=6$ forbidden $A_i$ for $v_3$. It follows that you can choose $(v_1,v_2,v_3)$ in $$20\cdot2\cdot 15+20\cdot 15\cdot 14=4800$$ ways, giving rise to ${1\over6}\cdot4800=800$ different triangles.

The tip of an isoscles triangle can be chosen in $20$ ways, and then the base in $8$ ways. Since there is no equilateral triangle possible it follows that there are $160$ isosceles triangles.

The total number of admissible triangles therefore is $640$.

$\endgroup$
3
$\begingroup$

We will show that the number of non-isosceles (scalene) triangles that can be formed whose vertices are among the vertices of a regular polygon of $n$ sides but whose sides are not the sides of the polygon is $$2n\left(\left[\frac{n-7}{2}\right] + \left[\frac{n-10}{2}\right]+\cdots \right)$$ where $[\cdot]$ is the greatest integer function. In particular, when $n=20$, there are $$40\left(\left[\frac{13}{2}\right] + \left[\frac{10}{2}\right]+ \left[\frac{7}{2}\right]+\left[\frac{4}{2}\right] \right) = 640$$ triangles.

We start with counting the number of triples $(d_1, d_2, d_3)$ such $2 \leq d_1 < d_2 < d_3$ and $d_1+d_2 +d_3 = n$. Putting $x_i = d_i-1$, we need the number of solutions $(x_1, x_2, x_3)$ such that $x_1 < x_2 < x_3$ and $x_1 + x_2 + x_3 = n-3$.

For any positive integers $N, p$ let $Q(N,p)$ denote the number of solutions to $$x_1 + x_2 + x_3+ \cdots +x_p = N$$ with $x_1 < x_2 < x_3 < \cdots < x_p$ and $P(N,p)$ denote the number of solutions to $$x_1 + x_2 + x_3+ \cdots +x_p = N$$ with $x_1 \leq x_2 \leq x_3 \leq \cdots \leq x_p$. We can call these solutions as distinct $p$ partitions of $N$ and $p$ partitions of $N$ respectively.

If $(x_1, x_2, \ldots, x_p)$ is a distinct $p$ partition of $N$, then $(x_1, x_2-1, x_3-2, \ldots, x_p-(p-1))$ is a $p$ partition of $N - \frac{1}{2}p(p-1)$ and similarly if $(y_1, y_2, \ldots, y_p)$ is a $p$ partition of $N - \frac{1}{2}p(p-1)$, then $(y_1, y_2+1, \ldots, y_p+(p-1))$ is a distinct $p$ partition of $N$. Hence we have

$$Q(N,p) = P\left(N-\frac{1}{2}p(p-1), p\right)$$

Again, if $(x_1, x_2, \ldots, x_p)$ is a $p$ partition of $N$, then $(x_1-1, x_2-1, \ldots, x_p-1)$ is a partition of $N-p$ with at most $p$ parts. Thus $$P(N,p) = P(N-p, 1) + P(N-p, 2) + \cdots + P(N-p, p)$$

Replacing $N$ by $N-1$ and $p$ by $p-1$ we get $$P(N-1,p-1) = P(N-p, 1) + P(N-p, 2) + \cdots + P(N-p, p-1)$$ Hence

$$P(N,p) = P(N-p, p) + P(N-1, p-1)$$ We need $Q(n-3, 3)$. Noting that $P(m,2) = \left[\frac{m}{2}\right]$ for any positive integer $m$, we have \begin{align*} Q(n-3,3) &= P(n-6, 3) \\ &= P(n-9,3) + P(n-7, 2) \\ &= P(n-9, 3) + \left[\frac{n-7}{2}\right] \\ &= P(n-12, 3) + P(n-10, 2) + \left[\frac{n-7}{2}\right] \\ &= P(n-12, 3) + \left[\frac{n-10}{2}\right] + \left[\frac{n-7}{2}\right] \end{align*}

Hence we have $$Q(n-3, 3) = \left[\frac{n-7}{2}\right] + \left[\frac{n-10}{2}\right]+\cdots $$

For any distinct 3 partition $(d_1, d_2, d_3)$ of $n-3$ we obtain two non isosceles triangles with one of the vertices as $A_i$: $(A_i, A_{i+d_1}, A_{i+d_1+d_2}$ and $(A_i, A_{i-d_1}, A_{i-d_1-d_2})$ where all additions and subtractions are modulo $n$ and the vertices are named as $A_0, A_1, \ldots, A_{n-1}$. Hence the number of distinct triangles is $$2n\left(\left[\frac{n-7}{2}\right] + \left[\frac{n-10}{2}\right]+\cdots \right)$$

Updated on 5 December 2016:

Is it possible to find a closed form for $$Q(n-3, 3) = \left[\frac{n-7}{2}\right] + \left[\frac{n-10}{2}\right]+\cdots $$ Yes, one can obtain the following: \begin{equation} Q(n-3,3)= \begin{cases} \frac{1}{12}(n-6)^2, &\text{if $n = 0\mod 6$;}\\ \frac{1}{12}((n-6)^2-1), &\text{if $n = 1\mod 6$;}\\ \frac{1}{12}((n-6)^2-4), &\text{if $n = 2\mod 6$;}\\ \frac{1}{12}((n-6)^2+3), &\text{if $n = 3\mod 6$;}\\ \frac{1}{12}((n-6)^2-4), &\text{if $n = 4\mod 6$;}\\ \frac{1}{12}((n-6)^2-1), &\text{if $n = 5\mod 6$;} \end{cases} \end{equation} How does one get the above forms?

Suppose that $n = 0\mod 6$. Now, compute the values of $Q(n-3,3)$ for some initial values, say $12, 18, 24, 30, 36, \ldots$. These are respectively $3, 12, 27, 48, 75, \ldots$. We use the Newton's interpolation formula. Given values $$ \begin{array}{ccccc} x_0 & x_1 & x_2 & x_3 & \cdots \\ f(x_0) & f(x_1) & f(x_2) & f(x_3) & \ldots \end{array} $$ \end{center} with $x_{i+1} - x_i = h$ for all $i$, we have, by Newton's formula $$f(x_0+th) = f(x_0) + \frac{t}{1!}\Delta f(x_0) + \frac{t(t-1)}{2!}\Delta^2 f(x_0) + \cdots $$ where $\Delta f(a) = f(a+h) - f(a)$ is the finite difference of $f$ at $x=a$.\ Consider the following difference table $$\begin{array}{cccc} n & Q(n-3,3) & \Delta & \Delta^2\\ 12 & 3 & & \\ 18 & 12 & 9 & \\ 24 & 27 & 15 & 6 \\ 30 & 48 & 21 & 6 \\ 36 & 75 & 27 & 6 \\ 42 & 108 & 33 & 6 \end{array} $$ Noting the second difference is a constant, writing $f(n) = Q(n-3,3)$ we obtain \begin{align*} f(n) =& f\left(12 + \frac{n-12}{6} \times 6\right) \\&= f(12) + \frac{\frac{n-12}{6}}{1!}\Delta f(12) + \frac{\frac{n-12}{6} \cdot \frac{n-18}{6}}{2!}\Delta^2 f(12) \\ &= 3 + \frac{9}{6}(n-12) + \frac{1}{12}(n-12)(n-18) \\ &= \frac{1}{12}(n-6)^2 \end{align*} Other expressions can be similarly obtained.

$\endgroup$
1
$\begingroup$

Total number of $\triangle = $no. of $\triangle$ with no side common $+$ no. of $\triangle$ with one side common $+$ no. of $\triangle$ with two sides are common

$\bullet\;$ Triangle with one side common $\displaystyle = \binom{n-4}{1} \times n$

$\bullet\;$ Triangle with two sides are common $\displaystyle = n$

So no. of $\triangle$ with no side common $$ = \binom{n}{3}-n(n-4)-n$$

Put $n=20$

$\endgroup$
  • 1
    $\begingroup$ You forget to get rid of the isosceles triangles. $\endgroup$ – achille hui Nov 17 '16 at 10:59
1
$\begingroup$

Given a regular polygon of $2n$ sides, start by counting all the distinct triangles that can be formed from the vertices of a $2n$-gon: $ \binom{2n}{3}. $ Then eliminate the ones that don't belong to the set by counting these disjoint sets of triangles:

  • Isoceles triangles. There are $n - 1$ different possible lengths for each of the equal sides, and $2n$ possible placements of the vertex between those sides, so $2n(n-1)$ such triangles if $n$ is not a multiple of $3$. (If $n=3k$ then the preceding procedure counts each equilateral triangle three times and we must remove the duplicates. Compare this answer.)
  • Triangles with exactly one side on the $2n$-gon. Note that no such triangle can be isoceles. There are $2n$ ways to choose the side on the $2n$-gon, and the third vertex can be any of the $2n-4$ points not adjacent to the vertices of the common side, so there are $2n(2n-4)$ such triangles.

There is no need for a third set of triangles consisting of those that share two sides in common with the $2n$-gon; those were included among the isoceles triangles.

The total number of triangles in all three excluded sets is $2n(n - 1) + 2n(2n-4) = 2n(3n-5)$. So the total number of scalene triangles not sharing a side with the $2n$-gon is $$ \binom{2n}{3} - 2n(3n-5). $$

Setting $2n = 20$, we have $$\binom{2n}{3} - 2n(3n-5) = \binom{20}{3} - 20(25) = 1140 - 500 = 640.$$

$\endgroup$
1
$\begingroup$

Let $a<b<c$ be the "sidelengths" of the triangle. The given conditions then enforce $$a=2+x_1,\quad b=3+x_1+x_2,\quad c=4+x_1+x_2+x_3$$ with $$x_i\geq 0\quad(1\leq i\leq 3),\qquad 3x_1+2x_2+x_3=11\ .\tag{1}$$ Choosing $x_1:=0, 1, 2, 3$ in turn produces $6+5+3+2=16$ solutions of $(1)$. Each of the $16$ resulting shapes can be placed in $40$ ways, hence there are $640$ admissible triangles in all.

$\endgroup$
0
$\begingroup$

No. of scalene triangles $$= C_{20}^3-180= \frac{20\cdot 19\cdot 18}{6} - 180 = 960$$

$\endgroup$

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.