# Number of triangles sharing all vertices but no sides with a given octagon

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?

• Why would you keep an odd number of vertices between vertices on an edge? $\{A,D,G\}$ is a perfectly fine triangle. – Patrick Da Silva Oct 13 '13 at 12:14

If two of the vertices are $A$ and $C$, what are the possible third vertex? Look at the whole list $A,...,H$

• Thanks Michael Got it. for $\bf{\{A,C,E,G\}}$ first we will select $2$ vertices from these for and then remaining select from $\bf{\{B,D,F,H\}}$. This can be done by $\displaystyle \binom{4}{2}\times \binom{4}{1} = 24$. similarly for $\bf{\{B,D,,F,H\}}$ first we will select $2$ vertices from these for and then remaining select from $\bf{\{A,C,E,G\}}$. This can be done by $\displaystyle \binom{4}{2}\times \binom{4}{1} = 24$ . So Total $= 24+24 = 48$ – juantheron Oct 13 '13 at 12:13

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,

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

• Thanks Professor got it. Total Triangle without any restriction is $\displaystyle = \binom{8}{3} = 56$. Total Triangle with one side common $\displaystyle = \binom{4}{1}\times 8 = 32$ and Total no. Triangle in which exactly two side common is $= 8$ – juantheron Oct 13 '13 at 12:41