Minimum number of questions in a multiple choice assignment

Question

Consider a class of $N$ students. I give them an assignment containing $M$ multiple choice questions ($M>0$). Each question is either right or wrong. The students give me back the scripts with their answers. Thus, for each student, I have one script containing $M$ questions and answers.

I decide to mark them using the following method:

1. I shuffle the students' scripts randomly. This way I have a pile of unmarked scripts in a random order.

2. I mark the first question for the first student. I put it in a second pile. This is the pile of "marked" scripts (with regards to the first question, as the other questions have not been marked yet).

3. I mark the first question for the second student. The position of this script in the "marked" pile depends on the answer of this second student and the answer of the student whose script is at the top of the "marked" pile (in this case, the first student):

   • (the "one-position upgrade" case): I put the second student's script immediately below that of the first student if the answer of the previous student was incorrect and the answer of this second student is correct.

   • (the "keeping the same order" case): I put the second student's script above that of the first student if the answer of this second student is incorrect; or if the answer of both students is correct.

4. Continue the marking of this first question for the rest of the students. Note that a script can only move up one step per question. However, a script can move down several steps per question. For example, it can reach the bottom if the answer was incorrect, and that of all those students who follow is correct.

5. Once the first question is marked for all student (so the "unmarked" pile is empty), pick up the "marked" pile and turn it around. Thus, if the first student had the first question correct, s/he is still at the top in the next round of marking.

6. Repeat 3/4/5 for the second and subsequent questions, until the $M_{th}$ question is marked.

7. Keeping the final ordering of scripts, grade them, by counting the number of correct answers. Thus, minimum grade is 0, and maximum is $M$.

Question: which is the minimum number of questions ($M_{min}$) that ensures (i.e. with complete certainty) that the final ordering of students follow a monotonic ordering of grades?

UPDATE: as the existing answer indicates, without further assumptions, there is no assurance a minimum number of questions will allow a monotonic grading. This is because one question can be non-informative, in the sense that all students are either correct or wrong, meaning there is no re-sorting of scripts' order.

So, to move further, assume that the probability that all students get the same answer (either right or wrong) in a given question is $p$. For the moment, take this probability to be independent of $N$ (a simplification, for sure).

My intuition:

• Naturally, $M_{min}$ will be a function of $N$, with positive partial derivative. I'm not sure about the second partial derivative. It might be constant.

• $M_{min}$ might be a concave, non-linear function of $p$. If $p=0$, all questions are informative, so the convergence is faster. However, if $p=1$, students have the same marks, so the initial ordering is by definition monotonic. Thus, if $p=1$, it is clear that $M_{min}=1$.

• However, for some $N$, $p$ is irrelevant. For example, it is clear that for $N \leq 2$, $M_{min}=1$, regardless of $p$.

Answer 1

If I understood correctly, without additional assumptions, there is no such $M$.

Consider the case when we have a single script with the highest grade, for which last answer is incorrect. And consider any number of questions $M$.

During last iteration this script will be put above the first in this iteration, thus after reverting the pile it will not be on top, so the ordering is incorrect, for any $M$.

EDIT: I did not consider another case when in last iteration the best script is already on top, but maybe someone can finish above reasoning for that case.

EDIT2: What if every script has grade $0$ except single one that has grade $1$ with last answer correct? If you start with this best script in the middle of the pile, in the last iteration it will move only 1 step, and won't be on top.