1
$\begingroup$

I feel really bad for asking so many questions... but just one more... there are 12 points that are equally spaced on a circle. Define a set of points $(A,B,C,D)$ NICE if $AB$ intersect $CD$. How many nice sets are there?

What I tries to do is counting in cases... there isn't any case when they are just one point away, and there is $1\cdot 9$ case when two points away , $2\cdot 8$ 3 points away until $5\cdot 5$ when 6 points away. there are 12 points in every cases and there are $2^3$ ways to arrange $A,B,C,D$. Wrapping this up, we will have:$$8\cdot12\cdot(1\cdot9+2\cdot8+3\cdot7+4\cdot6+5\cdot5)=9120$$

However this is no way near the answer. Can anyone tell where i did it wrong?

$\endgroup$
  • $\begingroup$ Uh i think i over-counted it... but i am too brain-dead to figure over-counts so can anyone just tell me the solution... $\endgroup$ – M. Chen Jan 2 '17 at 21:17
  • $\begingroup$ Are you counting sets of $4$ points or ordered $4$-tuples $\langle a,b,c,d\rangle$ such that $ab$ intersects $cd$? $\endgroup$ – Brian M. Scott Jan 2 '17 at 21:19
3
$\begingroup$

I’m assuming that you’re actually counting ordered $4$-tuples $\langle a,b,c,d\rangle$ of distinct points (chosen from the $12$) such that $ab$ intersects $cd$.

Let the points be $p_1,p_2,\ldots,p_{12}$ in order around the circle. Let $\{i,j,k,\ell\}$ be a $4$-element subset of $\{1,2,\ldots,12\}$, where $i<j<k<\ell$. Then $p_ip_k$ intersects $p_jp_\ell$. To get a $4$-tuple $\langle a,b,c,d\rangle$ from these $4$ points in such a way that $ab$ intersects $cd$, we can let $a$ be any one of the $4$. The choice of $a$ completely determines that of $b$: if $a=p_i$, $b$ must be $p_k$ and vice versa, and if $a=p_j$, $b$ must be $p_\ell$ and vice versa. We then have $2$ possible choice for $c$, after which $d$ must be the remaining point. Thus, there are $4\cdot2=8$ possible $4$-tuples using $p_i,p_j,p_k$, and $p_\ell$. Since there are $\binom{12}4=495$ ways to choose $4$ of the $12$ points, there are $495\cdot8=3960$ $4$-tuples $\langle a,b,c,d\rangle$ such that $ab$ intersects $cd$.

$\endgroup$
  • $\begingroup$ oh i see! so any 4 element from the set makes 2 perpendicular line and we just need to count the ways that they intersect. Thanks ! $\endgroup$ – M. Chen Jan 2 '17 at 21:37
  • $\begingroup$ @alex: Not literally perpendicular in general, but definitely intersecting, yes. You’re welcome! $\endgroup$ – Brian M. Scott Jan 2 '17 at 21:39
1
$\begingroup$

I initially got your same answer and my way of thinking was same as that of you. Then I got the error, we cannot just multiply with $2^3$ to take care of order of $4$ points in circle as intersection lines may differ. Corrected count must be as given below.

$2 \times 12 \times\left[\dbinom{1}{1}\dbinom{9}{1}+\dbinom{2}{1}\dbinom{8}{1}+\dbinom{3}{1}\dbinom{7}{1}+\dbinom{4}{1}\dbinom{6}{1}+\dbinom{5}{1}\dbinom{5}{1}+\dbinom{6}{1}\dbinom{4}{1}+\dbinom{7}{1}\dbinom{3}{1}+\dbinom{8}{1}\dbinom{2}{1}+\dbinom{9}{1}\dbinom{1}{1}\right]\\=3960$

$\endgroup$
  • $\begingroup$ Oh yeah! what is your motive behind this? Does it focus on counting stuff that will not cause overcount? I always use the wrong way when solving counting stuff... $\endgroup$ – M. Chen Jan 3 '17 at 0:17

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.