random intervals
- Thread starter radosr
- Start date
if im not mistaken... pairing to have an interval (a,b) intersecting all of the others means that for each (a_i, b_i) != (a,b) one has a_i < a, b_i > b.
so, (a,b) = (1005, 1006), a_i < 1005, b_i > 1006.
thus, suitable / total number of pairings:
\[\frac{1004!}{\binom{2010}{1005} \cdot 1005!}= \frac{1}{\binom{2010}{1005} \cdot 1005}\]
so, (a,b) = (1005, 1006), a_i < 1005, b_i > 1006.
thus, suitable / total number of pairings:
\[\frac{1004!}{\binom{2010}{1005} \cdot 1005!}= \frac{1}{\binom{2010}{1005} \cdot 1005}\]
- Joined
- 4/7/10
- Messages
- 14
- Points
- 13
The totol number ofpossible pairs (i.e the sample set ) :> 2010C2 *2008C2 * 2006C2 ..... 4C2 * 1
If one pair has to intersect all the other intervals (I assume it is (1,2010) ), we can have 1004 other distinct pairs , this can be done in : 2008C2 * 2006C2 .... 4C2 *1
The probability is => 2008C2 * 2006C2 .... 4C2 *1 / 2010C2 *2008C2 * 2006C2 ..... 4C2 * 1 => 1/2010c2 = 2/ 2010*2009 = 1/(1005*2009)
If one pair has to intersect all the other intervals (I assume it is (1,2010) ), we can have 1004 other distinct pairs , this can be done in : 2008C2 * 2006C2 .... 4C2 *1
The probability is => 2008C2 * 2006C2 .... 4C2 *1 / 2010C2 *2008C2 * 2006C2 ..... 4C2 * 1 => 1/2010c2 = 2/ 2010*2009 = 1/(1005*2009)
- Joined
- 2/10/11
- Messages
- 19
- Points
- 13
The total number of possible pairs is (2n-1)(2n-3)...3*1=(2n-1)!!
Since in each pairing there must be an interval (1,b) then if we denote by S_n the total number of pairings in case of 2n numbers, we will have S_n=(2n-1)S_(n-1), ... , S_2=3*S_1, S_1=1. After substitution, we will have S_n=(2n-1)!!
In case of your answer if 2n=4 4C2=6 but the answer is 3.
s*it! i should not post solutions when i'm about to go to bed! 'intersect' is not the same as 'included'
- Joined
- 2/10/11
- Messages
- 19
- Points
- 13
As I have posted, the total number of possible pairs for 2n numbers is S_n=(2n-1)!!
Now, using the same technique, we will get the answer of 2/3 as @peterruse mentioned.
In all cases there must be an interval (a, n) or (n,b) (overall (n-1)+n=2n-1 cases). If we remove this interval, we will have the same problem for 2n-2 numbers. After adding the removed interval, the interval that intersected all the others will intersect it as well since its length must be more than n-1. There is only one case when that interval is (n+1,2n), but in this case all the other intervals will intersect both all the others and the removed interval. So we have s_n=(2n-1)*s_n-1, ... , s_3=5*s_2, s_2=2*s_1, s_1=1. ( s_2=(2*2-1)s_1= 3*s_1 won't be correct since in this case there is no number between 1 and 2. If n>2 there is always a number before n which is essential for the intersection by the interval obtained for 2n-2 numbers). After substitution we get s_n=(2n-1)(2n-3)...7*5*2=(2/3)*(2n-1)!!.
Finally, P(n)=s_n/S_n=2/3 for all n.
Now, using the same technique, we will get the answer of 2/3 as @peterruse mentioned.
In all cases there must be an interval (a, n) or (n,b) (overall (n-1)+n=2n-1 cases). If we remove this interval, we will have the same problem for 2n-2 numbers. After adding the removed interval, the interval that intersected all the others will intersect it as well since its length must be more than n-1. There is only one case when that interval is (n+1,2n), but in this case all the other intervals will intersect both all the others and the removed interval. So we have s_n=(2n-1)*s_n-1, ... , s_3=5*s_2, s_2=2*s_1, s_1=1. ( s_2=(2*2-1)s_1= 3*s_1 won't be correct since in this case there is no number between 1 and 2. If n>2 there is always a number before n which is essential for the intersection by the interval obtained for 2n-2 numbers). After substitution we get s_n=(2n-1)(2n-3)...7*5*2=(2/3)*(2n-1)!!.
Finally, P(n)=s_n/S_n=2/3 for all n.
