Combinatorics - Topic

Member

Posts: 167

Joined: Oct 2 2014

Gold: 0.00

Apr 2 2016 10:37pm

suppose theres 40 dots spaced evenly in a circle. if i choose 4 different dots A,B,C,D wats the probabilty that the line segment AB intersect CD?
all i know is that the total outcomes is 40C4, but idk how to find number of ways AB intersects CD

will give fg to anyone who can help out. thanks

feanur

Member

Posts: 16,662

Joined: Nov 24 2007

Gold: 15,245.00

Trader: Trusted

Apr 3 2016 04:36am

First, I assume you choose A, B, C and D without using twice the same dot.

Let n be the number of dots.

Suppose A is chosen.

You now choose B. Number of possibilies = n-1.

A and B give you a partition of the remaining (n-2) dots, in two subsets of k and (n-2-k) dots :
k dots between A and B (clockwise), (n-2-k) dots between A and B (counter-clockwise).

For line CD to cross AB, you must choose C and D in different subsets.
(n-2)C2 choices for C and D (regardless of the order), k x (n-2-k) choices to have them in different subsets.

Do the sum for k = 0 to n-2 :

Σ k(n-2-k) = (n-1)(n-2)(n-3) / 6

Probability for the lines of crossing each other :

[ (n-1)(n-2)(n-3) / 6 ] / [ (n-1) x (n-2)C2 ] = 1/3

joeinfhills

Member

Posts: 16,796

Joined: Oct 15 2008

Gold: 19,640.61

Apr 3 2016 03:24pm

Quote (feanur @ Apr 3 2016 05:36am)

First, I assume you choose A, B, C and D without using twice the same dot.

Let n be the number of dots.

Suppose A is chosen.

You now choose B. Number of possibilies = n-1.

A and B give you a partition of the remaining (n-2) dots, in two subsets of k and (n-2-k) dots :
k dots between A and B (clockwise), (n-2-k) dots between A and B (counter-clockwise).

For line CD to cross AB, you must choose C and D in different subsets.

--> I made it this far. Then I got lost, what is C2?

(n-2)C2 choices for C and D (regardless of the order), k x (n-2-k) choices to have them in different subsets.

Do the sum for k = 0 to n-2 :

Σ k(n-2-k) = (n-1)(n-2)(n-3) / 6

Probability for the lines of crossing each other :

[ (n-1)(n-2)(n-3) / 6 ] / [ (n-1) x (n-2)C2 ] = 1/3

---> Bit rusty on my algebra, how does the term C2 drop out leaving only 1/3?

2 questions embedded in the quote above.... Wow!... learning something new everyday.

This post was edited by joeinfhills on Apr 3 2016 03:24pm

feanur

Member

Posts: 16,662

Joined: Nov 24 2007

Gold: 15,245.00

Trader: Trusted

Apr 3 2016 06:19pm

When a and b are natural numbers, a C b denotes the number of possibilities to choose b elements in a set containing a elements, regardless of the order you choose them.

Whenever b > a, a C b = 0.
Else,
a C b = a! / ( b! x (a-b)! )

Here, I wrote (n-2)C2 for : (n-2)x(n-3) / 2.

Go Back To Homework Help Topic List