4
$\begingroup$

How many ways are there to create a quadrilateral by joining vertices of a $n$- sided regular polygon with no common side to that polygon?

It's quite easy to solve for triangles for the same question, logic remains same, we need to choose $4$ vertices with none of them being consecutive, what I did is broke them into cases i.e.: {$n$ sided polygon}

$1)$ All $4$ consecutive - $n$ ways

$2)$ $3$ consecutive - $n (n-5)$ ways (draw a diagram and don't take the dots adjacent to chosen pair)

$3)\; 2+2$ consecutive - $n$ ways to choose the first pair, to choose the second, ways are $n-4-1=n-5$ so, total ways $\Rightarrow n(n-5)$

$4)\; 2$ consecutive strictly - $n$ ways, now to choose the other two, leaving the adjacent ones, we have $n-4$ left, so, $(n-6)(n-10)+2(n-8)$

According to me the answer is $\binom n4 - \{ n + n (n-5) + n(n-5) + ((n-6)(n-10)+(2)(n-8))n \}$ but for $n=20$, our teacher told us that answer is near to $200$ can somebody please confirm my or my teacher's answer?

$\endgroup$
  • $\begingroup$ true blue anil's answer is much better than mine, being generalized to $\frac{n}{n-k}\times{n-k\choose k}$ for counting the number of k-gons that can be created from the vertices of an n-gon such that the k-gon and n-gon have no common side. $\endgroup$ – Logophobic Jan 29 '16 at 15:04
  • $\begingroup$ @Logophobic: Thank you for your gracious comments. $\endgroup$ – true blue anil Jan 29 '16 at 15:51
3
$\begingroup$

Looking clockwise, attach one "general" vertex to each of the $4$ "special" vertices that will form the quadrilateral, viz, $\fbox{SG}$

Now there are $4$ boxes + $(n-8) = (n-4)$ entities.

Place the boxes in $\binom{n-4}{4}$ ways,
but as you actually have $n$, not $(n-4)$ vertices, multiply by $\frac{n}{n-4}$ to get

formula $=\frac{n}{n-4}\times\binom{n-4}{4}$

PS

Using black bullets for unused vertices, and white ones for quadrilateral vertices, create $4$ boxes $\boxed{\bullet\circ}\;$, each box to be treated as one unit. With $n=20$, say, the $4$ boxes can be placed anywhere in a string of $16$ units. A diagrammatic representation (in a straight line)is given below.
$\bullet\bullet\boxed{\bullet\circ}\bullet\bullet\boxed{\bullet\circ}\bullet\bullet\bullet\boxed{\bullet\circ}\bullet\boxed{\bullet\circ}\bullet\bullet\bullet\bullet$

The basic idea is that any such arrangement prevents adjacent vertices from being used.

$\endgroup$
  • $\begingroup$ sorry to ask, but a simple diagram would clarify it tremendously $\endgroup$ – Mrigank Jan 29 '16 at 15:41
  • $\begingroup$ I have added a diagram, but am incapable of depicting a convex polygon, so have shown it in a straight line. You can sketch it out properly. $\endgroup$ – true blue anil Jan 29 '16 at 17:49
  • $\begingroup$ True ball anil Nice explanation, Would you explain me the line, We have $n$ not $(n-4)$ virtices, So multiply by $\displaystyle \frac{n}{n-4}$, Thanks $\endgroup$ – juantheron Feb 20 '16 at 8:11
  • $\begingroup$ @juantheron: true blue anil, thank you. By creating boxes, we reduced the number of entities (= vertices in this problem) from $n$ to $n-4$. So each entity has only $(n-4)$ starting points, but it should have $n$ starting points, hence the multiplication factor. $\endgroup$ – true blue anil Feb 20 '16 at 10:43
2
$\begingroup$

$1)$ All $4$ consecutive $=n$ is correct

$2)$ $3$ consecutive $=n(n-5)$ is also correct

$3)$ $2\times2$ consecutive $=\frac{n(n-5)}{2}$ You were double-counting in this case $(a,b,d,e) = (d,e,a,b)$

$4)$ $2\times1\times1=\frac{n(n-6)(n-5)}{2}$ [edited - this expression is cleaner]

Collectively: \begin{align}&=n+2n\frac{(n-5)}{2}+n\frac{(n-5)}{2}+n(n-6)\frac{(n-5)}{2}\\&=n\left(1+(2+1+(n-6))\frac{(n-5)}{2}\right)\\&=n\left(1+(n-3)\frac{(n-5)}{2}\right)\\&=n\left(\frac{2+(n-3)(n-5)}{2}\right)\\&=n\left(\frac{n^2-8n+17}{2}\right)\\&=\frac{n^3-8n^2+17n}{2}\end{align} The final answer is:$${n\choose4}-\frac{n^3-8n^2+17n}{2}$$ Confirm: $n=8\implies2; n=20\implies2275$ (Your teacher said near $2000$, right?)

$\endgroup$
  • $\begingroup$ sorry, had sleep deprivation .. in 4th, I wanted to do something like firstly take the points at ends of valid space i.e. 2 are possible and each would have (n-6) choices and all others possiblities-> (n-6) would have n-something, cases overlapped $\endgroup$ – Mrigank Jan 28 '16 at 21:14
  • $\begingroup$ @ELiT then you wanted $\frac{n(n-6)(n-5)}{2}$, which is equivalent to what I originally posted as $4)$ -- I have reworked and edited my answer. $\endgroup$ – Logophobic Jan 28 '16 at 23:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.