0
$\begingroup$

A quadrilateral is formed by joining four vertices of a convex decagon. In how many ways can such a quadrilateral be formed if no two of its vertices are next to each other (that is, no two vertices of the quadrilateral must be neighbours in the decagon).

My attempt:

I tried to use inclusion exclusion principle, but I am making some mistake. Here's what I did:

If $ A_2, A_3, A_4$ are the sets that contain those selections where we have $2,3,4$ adjacent vertices respectively, then we have:

$n(A_2) = {10 \choose 1} \cdot { 8 \choose 2 } = 280 $

$n(A_3) = {10 \choose 1} \cdot { 7 \choose 1 } = 70 $

$n(A_4) = {10 \choose 1} \cdot { 6 \choose 0 } = 10 $

And,

$n(A_2 \cap A_3) = {10 \choose 1} \cdot { 7 \choose 1 } = 70 $

$ n(A_2 \cap A_4) = n(A_3 \cap A_4) = {10 \choose 1} \cdot { 6 \choose 0 } = 10 $

And,

$n(A_2 \cap A_3 \cap A_4) = { 10 \choose 1 } \cdot { 6 \choose 0 } = 10 $.

Thus, the answer must be: $$ { 10 \choose 4 } - ( 280 + 70 + 10 ) + ( 70 + 10 + 10 ) - ( 10 ) \\ = -70 $$

Which is clearly wrong.

$\endgroup$
  • 1
    $\begingroup$ If you want to do it using inclusion exclusion, probably the best strategy is to start with your universe of $\binom{10}{4}$ quadrilaterals, and then define sets $B_i$ to be the bad quadrilaterals containing $i$ and $i+1$ (including also $B_{10}$, the quadrilaterals containing 10 and 1). Now you have to figure out the overlaps among these, so as to apply inclusion-exclusion, but it's not too hard. $\endgroup$ – Hugh Thomas supports Monica Apr 6 '14 at 1:11
  • $\begingroup$ I think the figure for $N(A_2)$ is too big. It counts 1234 three times, instead of once, and it counts 1245 twice. $\endgroup$ – Gerry Myerson Apr 7 '14 at 11:11
1
$\begingroup$

You're only counting quadrilaterals where all $4$ vertices are adjacent, but you also need to account for the ones where two pairs of $2$ vertices are adjacent. Also I'm not sure how you're handling the order of the vertices; the way I'd do it is to label them, say, clockwise, so that you have $4\cdot\binom{10}4$ labeled quadrilaterals in all, and in the very end divide by $4$ to account for the $4$ possible labelings of the same quadrilateral; that way it's easier to keep track of the adjacency conditions.

You have four conditions, for the four pairs of (labeled) vertices that could be adjacent, and you want the quadrilateral to satisfy none of them, so you need to alternatingly add and subtract the numbers of quadrilaterals that satisfy any given subset of $k$ of the conditions. That's $4\cdot\binom{10}4$ for $0$ conditions, minus $4\cdot10\cdot\binom82$ for $1$ condition (since there are $4$ conditions to choose from and each is satisfied by $10\cdot\binom82$ quadrilaterals), plus $6\cdot10\cdot\binom71$ ($4$ of the $6$ pairs of conditions force a triple and $2$ don't, but the result is the same in either case), minus $4\cdot10$ (since any of the four sets of three adjacency conditions force all four vertices to be adjacent), plus $0$, since all four conditions can't be met simultaneously. That's

$$ 4\cdot\binom{10}4-4\cdot10\cdot\binom82+6\cdot10\cdot\binom71-4\cdot10=100 $$

Dividing by $4$ yields the result $25$.

This can be done a lot easier by attaching a "buffer" to every vertex, say, on the clockwise side, fixing the position of one such vertex-plus-buffer, distributing the remaining $3$ over the remaining $10-2-3=5$ positions, for $\binom53=10$ possibilities, and noting that the proportion of desired quadrilaterals that contain the initial fixed vertex is $4/10$, so the result has to be multiplied by $10/4$, yielding $25$.

| cite | improve this answer | |
$\endgroup$

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.