1
$\begingroup$

This question already has an answer here:

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 recognise 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.

$\endgroup$

marked as duplicate by Deusovi Aug 25 at 21:22

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1
$\begingroup$

The solution to the 100 Prisoner's problem works here. Give every student a number between $1$ and $n$, and let the $i$th student start with the $i$th test from the top. Then, assume this is the $j$th person's test, then check the $j$th test from the top. Keep on following this; all the students will find their own test iff there is no cycle greater than $\frac{n}{2}$ in size. The probability of there being a cycle greater than this in size is at least $ln(2)$, giving a lower bound of $1-ln(2)$.

I typed this up in a hurry, there may be errors.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.