There are 100 students taking an exam. The professor calls them one by one and asks each student a single person question: “How many of 100 students will have a “passed” mark by the end of this exam?” The students answer must be an integer. Upon receiving the answer, the professor immediately publicly announces the student’s mark which is either “passed” or “failed.” After all the students have got their marks, an inspector comes and checks if there is any student who gave the correct answer but got a “failed” mark. If at least one such student exists, then the professor is suspended and all the marks are replaced with “passed.” Otherwise no changes are made. Can the students come up with a strategy that guarantees a “passed” mark to each of them? Denis Afrizonov
Problem
Source: International Olympiad of Metropolises 2019 Problem 4
Tags: combinatorics, Kvant
04.09.2019 15:12
The strategy is quite simple. If the professor has already failed $k$ students, the student in line should say $99-k$. Then the final student to fail will have provided the correct answer.
04.09.2019 16:20
There is a strategy using induction. Indeed for $n=2$ first says $1$ and if he passes the second says $1$ as well. Otherwise the second says $0$. Now, let $A_n$ be the strategy for a particular $n$. We will find one for $n+1$ as well. Indeed, the first says $n$. If he fails we can apply on the remaining $n$ people the strategy $A_n$ found above since the goal for the teacher is the same (not to pass all of the remaining ones). If he passes we apply $A_n$ with each answer increased by $1$ (taking into account the first student). Since, the goal for the teacher is still the same, this will work too.
08.09.2019 18:25
Each student follows the following strategy: For each student $A_i$, Let the number of students who failed so far be $f_i$. Then student $A_i$ should say $99-f_i$. It's easy to see that this works. Suppose the number of students who failed afterall is $F \geq 1$. Then look at the last student who failed; $A'$. $A'$ said $99-(F-1)= 100-F$. His answer is right, so all students pass.
23.07.2021 20:41
Let $f(i)$ denote the number of passes after the $i$-th student where $i \in \{1,...,100\}$ and let each student guess $f(i-1)+100-i$ note that clearly either the last student to fail guesses the number correctly or there is no such student. $\blacksquare$