The number of triangles whose vertices are the the vertices of the vertices of an octagon but none of whose sides happen to come from the sides of the octagon.
My Attempt: Let $\{A,B,C,D,E,F,G,H\}$ be the vertices of an octagon. It is given that none of the side of octagon is the side of the triangle, so we do not take consecutive points.
So we take either $\{A,C,E,G\}$ OR $\{B,D,F,H\}$ points out of which we will take only three points, because we have form a triangle.
So This can be done by $\binom{4}{3}+\binom{4}{3} = 8$
But the only options given are 24, 52, 48, and 16.
Where have I made a mistake?
$\endgroup$ 15 Answers
$\begingroup$If two of the vertices are $A$ and $C$, what are the possible third vertex? Look at the whole list $A,...,H$
$\endgroup$ 1 $\begingroup$Suppose the vertices are labelled $1,2,\dots,8$. Count the number of triangles for which one of the vertices is $1$. Then the second vertex, going around "clockwise" (let's say the octagon was represented that way) is among $3,4$ or $5$ (if we put one at $6$, the third vertex would be $7$ or $8$, which would give the triangle a side in common with the octagon). For each case you can count the number of options : three options for $3$, two for $4$, one for $5$, for a total of $6$. This gives us $6$ triangles that have a vertex at $1$.
The group $\mathbb Z / 8 \mathbb Z$ acts on the triangles by mapping the triangle with vertices $(a,b,c)$ to the triangle with vertices $(a+k,b+k,c+k)$ (where $k \in \mathbb Z / 8 \mathbb Z$ and you can consider $a,b,c \in \mathbb Z / 8 \mathbb Z$). It is not hard to see that each triangle has an orbit of size $8$ under this action.
So if we count the triangles by considering those who have a vertex at $1$ and then rotate them via the group action, we will triple count because each triangle has three vertices. Therefore the answer is $(6 \times 8)/ 3 = 16$.
Hope that helps,
$\endgroup$ 0 $\begingroup$Hints for the "small" problem at hand:
(i) How many triangles are there without any restrictions? (ii) How many triangles have exactly one side in common with the octagon? (iii) How many triangles have exactly two sides in common with the octagon?
We now consider the more general problem: Given a regular $n$-gon $P$, how many $r$-gons $Q$ with vertices from $P$ are there that don't share a side with $P$?
An admissible $r$-gon leaves $n-r$ unused vertices. Write a string of $n-r+1$ zeros, where the first and the last zero denote the same "distinguished" unused vertex. Choose $r$ of the $n-r$ slots between the zeros and insert an $1$ into these slots. You then have an encoding of an admissible $r$-gon.
There are ${n-r\choose r}$ ways to chose the slots, and there are $n$ ways to choose which vertex of $P$ should be the "distinguished" unused vertex. The total number $N$ of admissible $r$-gons $Q\subset P$ is then given by $$N={n\over n-r}{n-r\choose r}\ ,$$ because the choice of the "distinguished" unused vertex has to be discounted. For $n=8$ and $r=3$ one obtains $N=16$.
$\endgroup$ 1 $\begingroup$There are a few conflicting answers here. The correct count is 16.
One approach (in a comment by @juantheron) is to consider all triples of vertices and subtract those that share exactly one side with the octagon and those that share exactly two sides with the octagon:$$\binom{8}{3} - 8\cdot 4 - 8 = 56 - 32 - 8 = 16.$$
A similar approach is to use the inclusion-exclusion principle. Start with all triples of vertices, subtract (an overcount of) those that share at least one side, and add back in those that share two sides:$$\binom{8}{3} - 8\cdot 6 + 8 = 56 - 48 + 8 = 16.$$
Here is the explicit list of 16:
ACE, ACF, ACG, ADF, ADG, AEG, BDF, BDG, BDH, BEG, BEH, BFH, CEG, CEH, CFH, DFH
Anyone who claims a count higher than 16, please show me one that is not on this list.
$\endgroup$ $\begingroup$From 8 vertices, three will make a triangle. So $8C3$ = $56$ but sides are not to be included and one side will be forming a side of triangle so deducting 8 from 56 we will get 48 which is the answer.
$\endgroup$ 1
