tag:blogger.com,1999:blog-4115025577315673827.post9049237321494095275..comments2020-07-30T14:44:21.349+05:30Comments on CSE Blog - quant, math, computer science puzzles: Probability of Grade A or BPratik Poddarhttp://www.blogger.com/profile/11577606981573330954noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-4115025577315673827.post-66180931779222362052011-01-20T16:30:02.246+05:302011-01-20T16:30:02.246+05:30I had already posted the same problem earlier :P
...I had already posted the same problem earlier :P<br /><br /><a href="http://pratikpoddarcse.blogspot.com/2009/10/find-your-number.html" rel="nofollow">http://pratikpoddarcse.blogspot.com/2009/10/find-your-number.html</a><br /><br />@Dinesh and @Siddhant,<br />Your solutions are correct. Thanks. :)Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-75963799343549241682010-12-08T05:12:34.296+05:302010-12-08T05:12:34.296+05:30My interpretation of the question: Every student g...My interpretation of the question: Every student gets to pick n/2 papers and if his/her paper is in the pick, its counted as a success. If everyone succeeds, the class passes.<br /><br />The solution is for the n students to assign themselves a rank from 1 to n randomly. Let p(i) be the rank of the ith student. Upon going into the office, this student will pick up the p(i)th paper first. If it belongs to student j, his next pick will be p(j) and so on till he either finds his paper or he exhausts his n/2 choices. <br /><br />In effect, the students create a random permutation, overlay it on top of the professor's random permutation and the composition is yet another random permutation. Each student follows a cycle in this resulting permutation. If the cycle they pick has fewer than n/2 entries, they win. If every cycle is of length < n/2, everyone wins and passes.<br /><br />Success probability is the probability that there are no large cycles in a random permutation. If there exists a cycle of length > n/2, it will be the largest cycle of the permutation. Fix k > n/2. To have a cycle of length k, we have (nCk)*(k-1)!*(n-k)! ways = n!/k ways. So the probability is 1/k and the success probability is 1-\sum_{k=n/2+1}^n (1/k) = 1 + H_n - H_(n/2). <br /><br />If n is odd, n/2 is replaced with ceil(n/2). By considering even and odd n separately, we can show that they are both decreasing and bounded below => Limit exists and is equal to 1 - ln(2) = 30.69%. For any finite n, there is a strategy with success prob 1 + H_n - H(n/2) > 30%.<br /><br />I have seen a related problem and solution before. I don't take any credit for this solution. Also, I remember reading a wonderful exposition on how to approach this problem and how in some sense the permutation approach is the "natural" approach to solve this. Unfortunately, I can't trace down that link. Finally, there is also a proof that this is the best strategy possible.Dinesh Krithivasanhttps://www.blogger.com/profile/13437484936096983201noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-38552052425240828122010-12-08T03:23:12.706+05:302010-12-08T03:23:12.706+05:30I am confused by the wording. The initial arrangem...I am confused by the wording. The initial arrangement is random and the student doesn't know which paper in the stack is his. But lets say he chooses n/2 papers at random and looks at all of them. If his paper is in that stack, will he recognize it? In other words, is this problem all about devising a strategy that maximizes the students' chance of finding their own paper? If so, the binary grading doesn't really matter. The student will see his/her paper and know his/her marks. And everyone passes if everyone knows their marks accurately.<br /><br />Is this the correct interpretation?Dinesh Krithivasanhttps://www.blogger.com/profile/13437484936096983201noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-36126161521196991622010-12-08T02:45:46.482+05:302010-12-08T02:45:46.482+05:30a soln can be found at http://www.math.dartmouth.e...a soln can be found at http://www.math.dartmouth.edu/~pw/solutions.pdfsidhttps://www.blogger.com/profile/04179126136399818676noreply@blogger.com