A professor interviews n students, and each student enters the interview in turn. The student only needs to answer how many people can pass the interview. The professor can freely decide whether the student passes according to the number of students who answered, and then make it public so that all students know the result. After all the interviews are over, if all the students pass the interview, or if there is a student who fails the interview but answers the number of people who passed the interview correctly, then the student wins, otherwise the professor wins.
- who has the definite win strategy when n=3?
- what if n=100?
I tried with brute force. but failed when n>=3 because there are so many potential outcomes...but if it's n=2, then the definite win strategy is the first one says 1. Then if the professor passes him, the second one says 1 again. If professor fails the first people, then the second one says 0.
But the brute-force search approach does not work for n>=3 because there is so many potential conditions...any smarter solutions?
Just for brevity, I'll use "error" to describe the case where the professor fails a student, but that student's number turns out to be the total number of pass replies, causing the students to win.
It helps to think about this in reverse order. The final student $s_n$ knows how many previous students got a pass, say $P_{n-1}$. If they say that same number $P_{n-1}$, then failing that student is immediately an error. So this forces the professor to either pass that last student or make an error.
We don't yet know that's actually always a best strategy for student $s_n$, but forcing a professor action seems helpful, so let's suppose the students have agreed the last student in will do just that. Now think about the second-to-last student, $s_{n-1}$. When this student must interview, they know the number of previous pass results $P_{n-2}$, and also know the professor will need to pass the last student to avoid an error. So if $s_{n-1}$ gives the number $P_{n-2}+1$, this similarly forces the professor's reply. If the professor fails $s_{n-1}$, then passing $s_n$ would be an error for $s_{n-1}$, but failing $s_n$ would be an error for $s_n$. So the professor can only avoid making an error by passing both $s_{n-1}$ and $s_n$.
The same reason works inductively for each students, who always knows the number of pass results so far, and that the following students have a strategy such that the professor must either pass all the following students or make an error. So stating the number which would result from failing the current student then passing all the remaining students sets up a situation where the professor either passes the current student and all remaining students, or else makes an error now or later.
To sum up, the students all agree that the $k$-th student to be interviewed will say the number $P_{k-1} + n-k$, where $P_{k-1}$ is the number times the professor has passed a student so far, and $(n-k)$ is the number of other students still to be interviewed. In other words, they give the number which would be the final pass count if the professor were to fail the current student then pass all the remaining students. Given this strategy, if the professor fails any student, the last student with a fail result correctly predicted the total number of passes, and the students win. The only other possibility is that the professor passes all students, which also means the students win.