0
$\begingroup$

Given the following problem :

A group of students got homework assignment where they need to pick a group of  functions and sort them .The students need to pick 5 pairs of functions and prove  some relation between them. 

1.Given that there are 16 function in the group , how many pairs can we have ?

Answer : Using C(n,k) , we have C(16,2) = 16 above 2 = 120 , hence , we have 120 options for pairs .

2.Assuming that each student chose randomly the 5 pairs independently , what's the

probability that two students chose the exact same 5 pairs of functions ?

Answer : probability for choosing 5 function is : $5/120$ , where $120$ was calculated

in the previous exercise . Hence , the probability for two students to choose the exact

same functions is : $(5/120)^2$ .

3.Assume that we have 100 students , find the upper bound to the probability that there

are two students with the exact same 5 functions

Answer : $C(100,2)∙(5/120)^2$ = $4950 ∙ (5/120)^2 $

I'd appreciate any feedback and/or corrections regarding this exercise

Regards

EDIT :

Trying to fix part (3) :

Answer : ${\binom{100}2} ∙ \frac1{\binom{120}5}$

1 Answers 1

2

Your calculation that there are $\binom{16}2=120$ possible pairs of functions is correct, but after that you go astray. By the same reasoning that you used in (1), there are $\binom{120}5$ different sets of $5$ pairs that a student could choose. Now consider the probability that students $A$ and $B$ choose the same $5$ pairs. Whichever $5$ pairs $A$ chooses, $B$ has $1$ chance in $\binom{120}5$ of choosing the same set of $5$ pairs, so the answer to (2) is $\frac1{\binom{120}5}=\frac1{190,578,024}\;.$

I’m not sure just what sort of calculation they’re looking for in (3). Suppose that no two students pick the same $5$ pairs. Then altogether they’ve chosen $100$ of the $\binom{120}5$ possible sets of $5$ pairs; there are $\binom{\binom{120}5}{100}$ ways to do this. They can choose a collection of $100$ sets of $5$ pairs in $100!$ different orders, so there are $\binom{\binom{120}5}{100}100!$ different ways in which they could end up all having different sets of pairs. Since there are $100^{\binom{120}5}$ ways for them to choose pairs, the probability that no two choose the same $5$ pairs is $\frac{\binom{\binom{120}5}{100}100!}{100^{\binom{120}5}}\;,$ and the probability that some two of them choose the same set of pairs is $1-\frac{\binom{\binom{120}5}{100}100!}{100^{\binom{120}5}}\;.$ Abbreviating $\binom{120}5$ as $n$, we can write this as $1-\frac{\binom{n}{100}100!}{100^n}=1-\frac{n!}{(n-100)!100^n}\;.$ For a very crude estimate we can note that $\frac{n!}{(n-100)!}>1\;,\tag{1}$ so $\frac{n!}{(n-100)!100^n}>\frac1{100^n}\;,$ and $1-\frac{n!}{(n-100)!100^n}<1-\frac1{100^n}\;.$

Of course the estimate in $(1)$ can easily be improved to give a better upper bound. For example, $\frac{n!}{(n-100)!}>(n-99)^{100}\;,$ so $1-\frac{n!}{(n-100)!100^n}<1-\frac{(n-99)^{100}}{100^n}\;.$

  • 0
    @ron: The reasoning used in your update to (3) doesn’t work. If there were $5$ functions instead of $16$, and $3$ students instead of $100$, the probability of a given pair of students picking the same $5$ pairs of functions would be $1/\binom{10}5=1/252$, and your reasoning would give an upper bound of $\binom32\frac1{252}\approx 0.012$, but the actual probability for which this is supposed to be an upper bound is more than $1-10^{-113}$.2012-04-11