The Ultimate Polygon Challenge

A different approach. Take a vertex of the polygon. We have $100$ gaps around it that we must divide into $4$ parts where each part is a length of at least $2$ gaps.

This is equivalent to $100 - 4$ = $96$ gaps that we have to divide into $4$ parts with length of each at least $1$ gap.

Now we can use the Stars and Bars formula to calculate. So that's $\binom{95}{3}$ = $138415$ number of quadrilaterals for one vertex.

We must consider for $100$ vertices but when we do that we have to adjust for the quadrilaterals repeated $4$ times.

So the final tally is $\frac{100} { 4} = 25$

$25 * 138415$ = $3460375$

First let's count the number of quadrilaterals that can be formed from a single vertex. Let's pick a vertex and name it 1. Once we've defined the first vertex, the others can be named 2,3,..100.

Each formed quadrilateral will be indicated as an ordered quadruple $\left(1, x, y, z\right)$ . We need to count how many of those quadruples that correctly represents a quadrilateral exist, which we can do in the following way: we can establish a 1-1 correspondence from $(1,a,b,c)$ (with $1<a<b<c$ ) to $(1,a+1,b+2,c+3)$ , where, if $c+3\leq 99$ , the transformed quadruple only has non-adjacent vertexes that form the quadrilaterals we want. So, all we have to do is count in how many ways we can choose the 3 different numbers $a$ , $b$ and $c$ , which range from $2$ to $96$ . This can be done in $\binom{95}{3}$ ways.

Now, if we were to draw all the possible quadrilaterals from each vertex, we will have to draw $100\cdot\binom{95}{3}$ quadrilaterals, where we are repeating each quadrilateral $4$ times, because it was drawn one time for each of its $4$ vertexes. We conclude that the number of quadrilaterals that can be formed is $\frac{1}{4}\cdot100\cdot\binom{95}{3} =3460375$

WLOG pick a vertex of 100 sided polygon. Leaving aside neighboring two out of remaining 97 any three can be selected but not contiguous ones, in 95C3 ways = 138415. Now there are 100 times such quadrilaterals each having 4 vertices hence multiple counts to be removed by multiplying this combination with (100/4) = 25. Answer: 138415 x 25 = 3460375

Take four number in ascending order $a,b,c,d$ which represent the number of vertices. If we transform it into the couple $a,b+1,c+2,d+3$ we will be almost sure that there is no pair of the closest vertices. So, since we have $100$ vertices we have to be sure that $a>=1$ and $d+3<=100$ . Therefore, we can choose $\binom{97}{4}$ .

However, if we have the pair $a=1, d=97$ than we have an edge between the vertices $1$ and $100$ . Therefore we have to exclude all of them. Using the same logic we can see that we can chose from the range $b+1>=3$ and $c+2<=98$ therfore, $b,c \in [2;96]$ and the total number of such quadrilaterals is $\binom{95}{2}$ .

The answer is $\binom{97}{4} - \binom{95}{2}=3460375$

This is a bit of deductive approach, starting from an 8-sided polygon going up. (No polygon with less than 8 sides will give a solution.) I manually counted the solutions for polygons having 8, 9, 10, and 11 sides to infer a general formula for an n-sided polygon. First, pick any vertex, count the solutions, then move to the second adjacent, irrelevant if clockwise or counterclockwise, count, and so on and so forth.

8-sided polygon: $2$ solutions: $1$ starting from the $1^{st}$ vertex, $1$ from the $2^{nd}$ (and $0$ from the rest.) PS: I'll show the details of these solutions in a note at the end.

9-sided polygon: $9$ solutions: $4$ from the $1^{st}$ vertex, $4$ from the $2^{nd}$ , $1$ from the $3^{rd}$ .

10-sided polygon: $25$ solutions: $10$ from the $1^{st}$ vertex, $10$ from the $2^{nd}$ , $4$ from the $3^{rd}$ , $1$ from the $4^{th}$ .

11-sided polygon: $55$ solutions: $20$ from the $1^{st}$ vertex, $20$ from the $2^{nd}$ , $10$ from the $3^{rd}$ , $4$ from the $4^{th}$ , $1$ from the $5th^{th}$ .

I noticed that the number of polygons for the $1^{st}$ vertex is always the same as that of the $2^{nd}$ , and the number decreases afterwards. And these numbers correspond to binomial coefficients: $20 = {6 \choose 3}$ , $10 = {5 \choose 2}$ , $4 = {4 \choose 1}$ , and all the parameters depend on the number of vertices of the polygon.

Let a = number of solutions

11-sided polygon: $a = {6 \choose 3} + {6 \choose 3} + {5 \choose 2} + {4 \choose 1} + {3 \choose 0} = 20+20+10+4+1=55$

10-sided polygon: $a = {5 \choose 2} + {5 \choose 2} + {4 \choose 1} + {3 \choose 0} = 10 + 10 + 4 + 1 = 25$

9-sided polygon: $a = {4 \choose 1} + {4 \choose 1} + {3 \choose 0} = 4 + 4 + 1 = 9$

8-sided polygon: $a = {3 \choose 0} + {3 \choose 0} = 1 + 1 = 2$

So if we have an n-sided polygon, we're always starting from: ${n-5 \choose n-8}$ ,

Hence, for an n-side polygon, the solution is:

$a = {n-5 \choose n-8} + {n-5 \choose n-8} + {n-6 \choose n-9} + {n-7 \choose n-10} + ... + {6 \choose 3} + {5 \choose 2} + {4 \choose 1} + {3 \choose 0}$

Rearranging: $a = {n-5 \choose n-8} + \bigg[ {3 \choose 0} + {4 \choose 1} + {5 \choose 2} + {6 \choose 3} + ... + {n-7 \choose n-10} + {n-6 \choose n-9} + {n-5 \choose n-8} \bigg]$

$a = {n-5 \choose n-8} + \sum_{i=0}^{n-8} {3+i \choose i}$

And we have that: $\sum_{i=0}^{m} {i + \alpha \choose i} = {m + \alpha + 1 \choose m}$ (A corollary of the hockey stick identity).

So in our case: $\sum_{i=0}^{n-8} {3+i \choose i} = {n -4 \choose n-8}$ .

Finally, the solution for an n-sided polygon: $\boxed {a = {n-5 \choose n-8} + {n -4 \choose n-8}}$

For n = 100, $a = {95 \choose 92} + {96 \choose 92} = 3,460,375$

---

Note : For the individual solutions for polygons of 8, 9, 10, and 11 sides, pick a vertex at random and label it "A", then move to an adjacent one labeling it "B", and so and and so forth. The solutions are the following (skipping the one with 11 sides due to size):

8-sided polygon:

$\scriptsize {ACEG, BDFH}$

9-sided polygon:
$\scriptsize {ACEG, ACEH, ACFH, ADFH}$

$\scriptsize {BDFH, BDFI, BDGI, BEGI}$

$\scriptsize {CEGI}$

10-sided polygon:
$\scriptsize {ACEG, ACEH, ACEI, ACFH, ACFI, ACGI, ADFH, ADFI, ADGI, AEGI}$

$\scriptsize {BDFH, BDFI, BDFJ, BDGI, BDGJ, BDHJ, BEGI, BEGJ, BEHJ, BFHJ}$

$\scriptsize {CEGI, CEGJ, CEHJ, CFHJ}$

$\scriptsize {DFHJ}$