Probability of Grade A or B
Source: Homepage of Tejaswi Navilarekallu, Post Doctoral Fellow, Vrije Universiteit, Amsterdam
Problem:
A professor decides the following grading scheme in his class. After the final exam is graded, he keeps all the papers upside down on his table in a random order so that no student can recognize his own paper. Each student during his turn can overturn at most n/2 of these papers (where n is the total number of students in the class) and guess whether he received an A or a B on the final (there are only two grades given). Obviously the student doesn't know which paper is his, so it is not guaranteed that he will find his own score by looking at n/2 scores. The papers are then turned back and kept in the original order. The students cannot pass any information to others. All the students pass the course if "everyone" guesses their grade correctly, and they fail otherwise. Come up with a strategy that the students can decide on beforehand, so that the probability that they all will pass is more than a positive constant independent of n.
Solution:
The solution discussed in a problem before at http://pratikpoddarcse.blogspot.com/2009/10/find-your-number.html
Problem:
A professor decides the following grading scheme in his class. After the final exam is graded, he keeps all the papers upside down on his table in a random order so that no student can recognize his own paper. Each student during his turn can overturn at most n/2 of these papers (where n is the total number of students in the class) and guess whether he received an A or a B on the final (there are only two grades given). Obviously the student doesn't know which paper is his, so it is not guaranteed that he will find his own score by looking at n/2 scores. The papers are then turned back and kept in the original order. The students cannot pass any information to others. All the students pass the course if "everyone" guesses their grade correctly, and they fail otherwise. Come up with a strategy that the students can decide on beforehand, so that the probability that they all will pass is more than a positive constant independent of n.
Solution:
The solution discussed in a problem before at http://pratikpoddarcse.blogspot.com/2009/10/find-your-number.html
a soln can be found at http://www.math.dartmouth.edu/~pw/solutions.pdf
ReplyDeleteI 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.
ReplyDeleteIs this the correct interpretation?
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.
ReplyDeleteThe 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.
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.
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).
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%.
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.
I had already posted the same problem earlier :P
ReplyDeletehttp://pratikpoddarcse.blogspot.com/2009/10/find-your-number.html
@Dinesh and @Siddhant,
Your solutions are correct. Thanks. :)