Pass-Fail
Recent Facebook Puzzle from Denis Afrisonov.
Share:Puzzle. 100 students took a test where each was asked the same question: “How many out of 100 students will get a ‘pass’ grade after the test?” Each student must reply with an integer. Immediately after each answer, the teacher announced whether the current student passed or failed based on their answer. After the test, an inspector checks if any student provided a correct answer but was marked as failed. If so, the teacher is dismissed, and all students receive a passing grade. Otherwise, the grades remain unchanged. Can the students devise a strategy beforehand to ensure all of them pass?
Alistair:
I can find a strategy such that the last student who fails gets the right answer. If the teacher does not want to be dismissed, he must therefore pass everybody.
19 July 2024, 10:03 pmIvan:
If the teacher considers the answer “zero” correct, this makes the answer incorrect. Therefore, the teacher must consider the answer “zero” incorrect. But if all students answer “zero”, in the end all their answers are correct. The inspector dismisses the teacher and all students pass.
20 July 2024, 6:51 amLeif:
Or the other way around – if all students say 100, then they must all be marked correct and everyone passes. If the teacher marks one student (or more) as wrong, the teacher is dismissed, and everyone passes.
Are we missing something? Because these answers fell a bit trivial.
20 July 2024, 10:06 amtanyakh:
Dear Ivan and Leif, the teacher is allowed to mark the incorrect answer as correct sometimes.
20 July 2024, 10:09 amLeo B.:
Suppose the teacher is clairvoyant. Then she picks the smallest number not mentioned by any of the students, considers that number the correct answer, and grades that number of answers as correct, rendering the rest incorrect.
Oh, and what if the smallest number not mentioned is 100, because all numbers in [0; 99] have been mentioned exactly once? Then she grades “1” as the correct answer, and the remaining 99 incorrect. The inspector will be satisfied.
Therefore, even if the teacher is not clairvoyant, she can achieve the same result by pure chance.
20 July 2024, 8:51 pmAndreas:
If I understand it correctly, each student will know whether the teacher passed or failed each previous student before they have to answer, and the inspector considers the correct answer to be the number of students that got a ‘pass’ grade from the teacher. In that case, each student could give the answer 99 minus the number of ‘fail’ grades so far, which is one less than the possible maximum if the teacher would only give out ‘pass’ grades from now on.
If the teacher grades all as ‘pass’ then they will all technically be incorrect but that doesn’t matter since they already passed. Otherwise, since everyone answers one less than the possible maximum, the last one who does not get a “pass” grade gets the right answer.
21 July 2024, 12:47 pmEvan:
The teacher chooses an integer x in [0, 100]. If x = 100, then all students pass and the result is trivial, so we restrict to x in [0, 99]. Note that |x| = 100.
The strategy the students agree on is follows: the first student answers ’99’. If the teacher announces this student passes, then all subsequent students answer ’99’. One student must be failed despite giving the correct answer and the teacher is dismissed.
If, however, the teacher announces that the first student fails, then the next student instead answers ’98’. The students repeat the same steps as above, either repeating the answer once a student has been passed or decreasing their answer by one on a fail. One student is always failed despite giving a correct answer and the teacher is dismissed.
I shall not provide a formal proof, but the reason this strategy works is because there are 100 students, and the teacher must select an x in [0, 99] for the number of students to pass. There are |x| = 100 options for the teacher to select. If the teacher selects x = 0, then all 100 students are failed, including the last student who answers ‘0’. For any x the teacher selects, there will be x + 1 students answering ‘x’. By the pigeonhole principle, one of these students must be failed despite giving the correct answer.
23 July 2024, 1:31 pmGennardo:
Every student adds the number of students that have already passed to the number of students who are behind him. To make it more convenient: the first student says 99 and every student says the number of his predecessor if his predecessor has passed, but subtracts 1 to the number of his predecessor if he had failed. The effect is that the last student that failed had the correct answer. So the students reached their goal which they do of course if the teacher let everybody pass.
23 July 2024, 3:00 pmPuzzled:
Could someone please tell if the following consideration is correct?
3 August 2024, 7:50 amEvery student answers with 0. If the teacher ranks them all as failed, in the end it will be every student having given the correct answer but marked as failed. If the teacher ranks someone as passed, it’s a case of a student having given an incorrect answer but marked as passed. Either way, the teacher is disqualified.
tanyakh:
to Puzzled.
Suppose every student answers 0. Then the teach can pass one of them and fail the others.
4 August 2024, 11:43 amMartin Roller:
The students answer with the numbers 0, 1, 2, up to 99. If the teacher fails at least one of them, some student guessed the right number of passes, so the teacher is dismissed and all students pass. If not, all students passed and the grades are not changed.
31 August 2024, 12:26 pmMartin Roller:
Ah well, I retract that. The teacher could pass the student giving the correct answer.
31 August 2024, 3:17 pmMartin Roller:
Bonus Puzzle: The strategy for the students, defined by Andreas et. al. is _unique_. If at least one student deviates from the strategy, the teacher can fail at least one student and the inspector won’t prevent it.
11 October 2024, 3:03 am