combinatorics
MY TRY:
We take a circle. On that circle we put four of the 12 points. Between those points there are 4 gaps. Each gap must have at minimum 1 point. Therefore by star and bars method-
a,b,c,d are the gaps:
$$a+b+c+d=8$$
$a,b,c,d\geq 1$:
$$a+b+c+d=4$$
which becomes $\binom{7}{3}$ = $\bbox[5px,border:2px solid red]{35}$.
However the answer is 105. Obviously I am missing a factor of 3. But I do not know how that will come in.
Consider a regular polygon with $n$ number of vertices $\mathrm{A_1, \ A_2,\ A_3, \ A_3, \ldots , A_{n-1}}$ & $\mathrm{A_{n}}$
Total number of triangles formed by joining the vertices of n-sided regular polygon $$N=\text{number of ways of selecting 3 vertices out of n}=\color{}{\binom{n}{3}}$$ $$N=\color{red}{\frac{n(n-1)(n-2)}{6}}$$ $\forall \ \ \color{blue}{n\geq 3}$
Consider a side $\mathrm{A_1A_2}$ of regular n-polygon. To get a triangle with only one side $A_1A_2$ common (As shown in figure-1 below)
(figure-1)
Join the vertices $A_1$ & $A_2$ to any of $(n-4)$ vertices i.e. $A_4, \ A_5,\ A_6, \ \ldots \ A_{n-1}$ to get triangles with only one side common. Thus there are $(n-4)$ different triangles with only one side $A_1A_2$ common. Similarly, there are $(n-4)$ different triangles with only one side $A_2A_3$ common & so on. Thus there are $(n-4)$ different triangles with each of $n$ sides common. Therefore, number of triangles $N_1$ having only one side common with that of the polygon $$N_1=\text{(No. of triangles corresponding to one side)}\text{(No. of sides)}=\color{blue}{(n-4)n}$$
(figure-2)
Now, join the alternate vertices $A_1$ & $A_3$ by a straight (blue) line to get a triangle $A_1A_2A_3$ with two sides $A_1A_2$ & $A_2A_3$ common. Similarly, join alternate vertices $A_2$ & $A_4$ to get another triangle $A_2A_3A_4$ with two sides $A_2A_3$ & $A_3A_4$ common & so on (as shown in above figure-2). Thus there are $n$ pairs of alternate & consecutive vertices to get $n$ different triangles with two sides common (Above fig-2 shows $n$ st. lines of different colors to join alternate & consecutive vertices). Therefore, number of triangles $N_2$ having two sides common with that of the polygon $$N_2=\color{blue}{n}$$ If $N_0$ is the number of triangles having no side common with that of the polygon then we have $$N=N_0+N_1+N_2$$ $$N_0=N-N_1-N_2$$ $$=\binom{n}{3}-(n-4)n-n$$ $$=\color{}{\frac{n(n-1)(n-2)}{6}-n^2+3n}$$ $$N_0=\color{red}{\frac{n(n-4)(n-5)}{6}}$$ The above formula $(N_0)$ is valid for polygon having $n$ no. of the sides such that $ \ \ \color{blue}{n\geq 6}$
There is a much stronger necessary (and in fact sufficient) condition than the triangle inequality:
It is a well-known fact that a quadrilateral with sides $a,b,c,d$ has an incircle iff $a+c=b+d$. Can you think of the reason for this?
So you have to count the number of quadruples $\{a,b,c,d\} \in \{1,2,3,4,5,6,7,8\}$ satisfying $a+c=b+d$. Can you continue from here?
Best Answer
There's 2 factors to take into consideration here:
no. of vertices remains constant
we actually have to use the gaps in between the vertices to obtain the result and not the vertices themselves
Lets say you have an n sided polygon and you're trying to find out how to construct an m sided polygon such that no side is common to the base polygon. We can start by considering the vertices to already have been selected, meaning m of n possible candidates have already been selected and that leaves us with (n - m) vertices. Now, m vertices in a polygon also generate m gaps in between them. Lets say that for any 2 corners 'A1' and 'A2' that are part of the m selected vertices there are V vertices in between them. Since there are m gaps, we can denote the number of unused vertices between 'Ai' and 'Aj' as V and since there are n-m unused vertices in total we can write:
V1 + V2 + V3 ...... V(m) = n-m
now if no side is to be common to the n sided polygon, that means the number of unused vertices between and 2 selected vertices has to be greater than 1. We can write V = V' + 1, therefore our new condition becomes:
-> V'1 + 1 + V'2 + 1 ..... V'(m) + 1 = n - m
-> V'1 + V'2 + V'3 ....... V'(m) + m = n - m
-> V'1 + V'2 + V'3 ....... V'(m) = n - 2m
Now the problem is like finding all non-zero integer solutions to this condition which happens to be C((n-2m)+(m-1),(m-1)) = C(n-m-1,m-1).
But the problem here is that it counts all the V' terms as distinct, like how (0,1) is different from (1,0) so we have to divide it by the number of cyclic permutations it can have which is (m-1)! (Reason is because corners are similar). Its not finished yet because we can rotate polygon n times meaning we should multiply by n.
The final result is ((n)*C(n-m-1,n-1))/(m-1)!
If I've done a mistake please do correct me.