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

  • $\begingroup$ Can you specify exactly what happens if the marked pile has more than one script already? Where does the new one go exactly? $\endgroup$ Commented Feb 24, 2017 at 12:54

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

  • $\begingroup$ Well, if $N=2$, $M_{min}=1$. That is a counterexample. $\endgroup$
    – luchonacho
    Commented Feb 24, 2017 at 15:59
  • $\begingroup$ Actually, it is perhaps possible to prove that such minimum exist. For instance, it seems "logical" that a number of questions equal to $N^{1000}$ would certainly provide a monotonic ordering. So, if there exists a number of questions which gives a monotonic ordering, maybe $N^{1000} - 1$ might also do. By some type of induction mechanism that I am not aware of, you can perhaps prove the existence of a minimum. $\endgroup$
    – luchonacho
    Commented Feb 24, 2017 at 16:13
  • $\begingroup$ @luchonacho Think about scenario in my last edit with $N = 4$ and let the best script be 2nd from the bottom, it will never reach top regardless of $M$. $\endgroup$ Commented Feb 24, 2017 at 16:19
  • $\begingroup$ Ah, now I understand it. You are right. That is an example where there is no $M$, basically because all the other questions were redundant. So in effect, the "useful" question was just one -- the last one. So, to move forward, I see two options: (i) have a conditional solution, or (ii) consider questions where not everyone is either correct or incorrect (the "useful" questions). Maybe, assuming that in each question, there is at least one correct and incorrect. Something like assuming questions are not easy enough, given the training level of students. $\endgroup$
    – luchonacho
    Commented Feb 24, 2017 at 16:25
  • $\begingroup$ Updated the question. $\endgroup$
    – luchonacho
    Commented Feb 28, 2017 at 10:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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