How many hexagons can be made by joining the vertices of a 15 sided polygon if none of the sides of the hexagon is also the side of the 15-gon.

combinatoricspermutations

How many hexagons can be constructed by joining the vertices of a 15 sided polygon if none of the sides of the hexagon is also the side of the 15-gon.

Suppose, we take a 9 sided polygon and use Gap Method (Gap and string method in permutations and combinations) to fill other 6 points to be filled in between the present 9 points in order to have a 15 sided polygon

Also, in order to make hexagon according to the question, we just have to choose 6 "gaps" between the present points and put the points in the places. So, by doing all this we will have a 15 sided polygon.

And in this way, no. of ways of making a 15 sided polygon will mean same as selecting 6 points from a 15 sided polygon which aren't adjacent. (which helps in the idea of making a hexagon which will have no side which is also a side of the 15 sided polygon)

[ "×" – present points, "_" – gaps]

                    ×         _            ×
                  _                          _ 
                  
                 ×                             ×
                  _                            _           

                    ×                          ×
                      _                       _
                        ×                   ×
                            _            _
                                   ×

No. of gaps=9

So, now according to me,

No. of such Hexagons which can be formed = $\binom{9}{6}$
= 84

But, this is not the correct answer. What am I missing?

(Correct Answer- How many hexagons can be constructed by joining the vertices of a 15 sided polygon if none of the sides of the hexagon is also the side of the 15-gon.)

Best Answer

The $15$-sided polygon is a fixed object. You need a reference point. Say it is vertex $A$.

There are two possibilities: vertex $A$ is a vertex of the hexagon, or it is not.

Suppose $A$ is not a vertex of the hexagon. Arrange nine blue balls in the form of a circle. Label one of those balls $A$. Choose six of the nine gaps in which to place a green ball to ensure that no two green balls are adjacent. Now label the vertices in alphabetical order as you proceed clockwise around the circle, starting at $A$. The letters on the green balls are the vertices of the hexagon. There are $\binom{9}{6}$ ways to do this, which agrees with your answer.

Now suppose $A$ is a vertex of the hexagon. Color it green. Arrange nine blue balls around $A$ to form a circle which includes the ball labeled $A$. Doing so creates $10$ spaces in which to place a green ball, but two of these are adjacent to $A$, leaving eight spaces where a green ball could be placed so that it is not adjacent to $A$. Choose five of these eight spaces in which to place a green ball to ensure that no two green balls are adjacent. Now label the balls in alphabetical order as you proceed clockwise around the circle, starting at $A$. The letters on the green balls are the vertices of the hexagon. There are $\binom{8}{5}$ ways to do this, which you have not taken into account.

Since the two cases are mutually exclusive and exhaustive, the number of admissible hexagons is $$\binom{9}{6} + \binom{8}{5}$$ which agrees with the linked answers provided by Andre Nicolas and Henry.

Related Question