Source: Homepage of Tejaswi Navilarekallu, Post Doctoral Fellow, Vrije Universiteit, Amsterdam
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.
The solution discussed in a problem before at http://pratikpoddarcse.blogspot.com/2009/10/find-your-number.html