tag:blogger.com,1999:blog-4115025577315673827.post6290620894644837588..comments2020-05-25T13:34:36.365+05:30Comments on CSE Blog - quant, math, computer science puzzles: Drunk GuestsPratik Poddarhttp://www.blogger.com/profile/11577606981573330954noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-4115025577315673827.post-73576886215803531842010-02-18T11:56:26.663+05:302010-02-18T11:56:26.663+05:30@VKC (Vivek Kumar Chaurasiya)
Thanx for the soluti...@VKC (Vivek Kumar Chaurasiya)<br />Thanx for the solutions. <br /><br />Regarding the first part:<br />Correct solution. Thanx a lot. I had not been able to solve it.<br />Just of clarify things, reposting:<br /><br />Considering 3 guests<br />p(A u B u C) = p(A)+p(B)+p(C) - p(AB) - p(AC) - p(BC) + p(ABC)<br /><br />p(A) means A spends the night in his room.<br /><br />p(A) = p(B) = p(C) = 1/3 = 1/n<br /><br />P(AB) = P(BC) = P(CA) = 1/n.1/(n-1)<br /><br />and so on<br /><br />So, p(A u B u C) = n*1/n - nC2 * 1/n*1/n-1 + + nCn 1/n*1/(n-1)*1/(n-2)<br /><br />So,<br />p(A1 u A2 u .. .. An) = 1 - 1/2! + 1/3! -1/4! and so on<br /><br />So, for n=5,<br />p(A1 u A2 u .. .. A5) = 1-1/2! + 1/3! -1/4! + 1/5!<br /><br />Required probability = (120-60+20-5+1)/120 = 76/120<br /><br />Also, as n approaches infinity, Required probability = 1-(1/e) :)<br /><br />Regarding the second part: Answer 1 is correct and there is a simpler method. U = P1 + P2 + .. Pn<br /><br />where Pi is one if guest i goes to the correct room and zero otherwise<br /><br />E(U) = E(P1 + P2 +.. Pn)<br />By linearity of expectation,<br />E(U) = E(P1) + .. E(Pn) = 1/n*n = 1<br />:)<br /><br />ThanxPratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-9518841109220230732010-02-16T17:35:10.989+05:302010-02-16T17:35:10.989+05:30Correction above:
~~~~~~~~~~~~~~~~~~~~~~~
p(A u B ...Correction above:<br />~~~~~~~~~~~~~~~~~~~~~~~<br />p(A u B u C) = p(A)+p(B)+p(C) - p(AB) - p(AC) - p(BC) + p(ABC)<br />~~~~~~~~~~~~~~~~~~~~~~~<br /><br />About Q2: What is the expected number of guests who end up in a room in which they were originally assigned? <br /><br />say D(n): no. of derangements of n objects<br /><br />So, E( guests who end up in a room in which they were originally assigned ) = U (say)<br />U = E(1) + E(2) + E(3) ....... ....... . . E(n)<br /><br />Now, E(j) = j . p(j) <br /><br />p(j) = probability that j persons goto their respective rooms while others dont.<br /> = nCj * D(j)/ n!<br /><br />U = Summation (j=1 to n) [ j * p(j) ]<br /><br />Concept part done till here. Rest all simplification steps will be guided by mathematics and series manipulations.<br /><br />Finally, U comes out to be = 1 (so, one can verify their solving)VKChttps://www.blogger.com/profile/14255977546255517276noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-46083980999709384782010-02-15T17:52:35.246+05:302010-02-15T17:52:35.246+05:30This problem is a simple extension of concept know...This problem is a simple extension of concept known as "Principle of De-rangement' which states that [none of the elements of the set appears in its original position]:<br /><br />p(A u B u C) = p(A)+p(B)+p(C) - p(AB) - p(AC) - p(BC) = p(ABC)<br /><br />Once can foresee (or by induction) that if we write such formula for 4 events or N events, then the minus sign will vary alternately. <br /><br />In our problem, if we find out p(123....N) (say Q) then the required probability = <br />(1 - Q)<br /><br />For e.g. if N=5;<br /><br />Total No. of permutations = 120<br />No. of permutations in which no person goes to his assigned room = 44 (deduce this from above stated principle ) <br /><br />So, required prob = 1 - (44/120)<br /><br />Hint:<br /><br />44 = 5! ( 1 - 1/1! + 1/2! - 1/3! + 1/4! - 1/5!)VKChttps://www.blogger.com/profile/14255977546255517276noreply@blogger.com