An Infinitude of Perfidious Pupils

Question

Here's an original puzzle I created. Enjoy!

A teacher had infinitely many students, and he referred to them by the designations $\text{Student } 0$, $\text{Student } 1$, $\text{Student } 2$, and so on. It happened that all of these students had limited eyesight. Specifically, for each $n$, Student $n$ could only see distances of $n$ yards or less. This teacher set up his classroom in a special way so that every student could see the board. He arranged all the desks in a straight line, with Student $0$'s desk immediately against the board (a negligible distance away), Student $1$'s desk $1$ yard away, Student $2$'s desk $2$ yards away, and so on, so that each of them could see the board from where they were sitting.

One day, the students had a pop quiz. They were instructed to turn their desks around so that they were all facing away from the board. (Looking at the board would be cheating, since useful information was written on it.) Right after he handed out the test, the teacher was called out of the room for an emergency, and the students were left unsupervised.

Simultaneously, some (or maybe none) of the students turned back to their original orientations to face the board, in an act of academic dishonesty. Immediately before the teacher reentered the room, all of these cheaters pivoted once more, so that the teacher could not see who had turned.

Suspicious of treachery, the teacher interrogated the students to find out who, if anyone had cheated. They made the following statements:

$\text{Student }0$: "I saw at most $1$ student cheat."

$\text{Student }1$: "I saw exactly $1$ student cheat."

$\text{Student }2$: "I saw at most $2$ students not cheat."

$\text{Student }3$: "I saw exactly $2$ students not cheat."

$\text{Student }4$: "I saw at most $3$ students cheat."

$\text{Student }5$: "I saw exactly $3$ students cheat."

$\text{Student }6$: "I saw at most $4$ students not cheat."

$\text{Student }7$: "I saw exactly $4$ students not cheat."

$\text{Student }8$: "I saw at most $5$ students cheat."

$\text{Student }9$: "I saw exactly $5$ students cheat."

$\text{Student }10$: "I saw at most $6$ students not cheat."

$\text{Student }11$: "I saw exactly $6$ students not cheat."

$\text{Student }12$: "I saw at most $7$ students cheat."

$\text{Student }13$: "I saw exactly $7$ students cheat."

$\text{Student }14$: "I saw at most $8$ students not cheat."

$\text{Student }15$: "I saw exactly $8$ students not cheat."

…

Student $4n$: "I saw at most $2n+1$ students cheat."

Student $4n+1$: "I saw exactly $2n+1$ students cheat."

Student $4n+2$: "I saw at most $2n+2$ students not cheat."

Student $4n+3$: "I saw exactly $2n+2$ students not cheat."

…

The teacher knows that every student who cheated told a lie and that every student who didn't cheat told the truth.

My challenges for you are:

a) Determine whether $\text{Student }20$ cheated.

b) Prove that the situation described above is not contradictory.

c) Bonus challenge: Determine precisely which students are those for whom the teacher can determine whether or not they cheated. (I don't know the answer to this!)

Notes:

• The students all turned simultaneously, so they only saw the actions of the people that they faced during the moment where some students were cheating.
• No student saw themself.
• The students have eyesight limitations. This means that $\text{Student }0$ didn't see any students, and that, for $n >0$, $\text{Student }n$ saw $\text{Student }0, \dots, \text{Student } n-1$ if $\text{Student }n$ cheated and that $\text{Student }n$ saw $\text{Student }n+1, \dots, \text{Student }2n$ if $\text{Student }n$ didn't cheat.

Answer 1

Let's assume $C(n)$ is the number of students that cheated, between $0$ and $n-1$, and for convenience, assume $c(n)$ is a function that returns $1$ if student $n$ cheated, and $0$ if not. If you'll notice, when a student cheats, they'll bring a lot of information with them, which we can use to make contradictions.

If $4n$ cheated, then $C(4n) > 2n+1$.

If $4n+1$ cheated, then $C(4n+1) \neq 2n+1$.

If $4n+2$ cheated, then $C(4n+2) < 2n+2$.

If $4n+3$ cheated, then $C(4n+3) \neq 2n+2$.

This problem essentially reduces to students making statement $A$ if they are nice and truthful, and statement $-B$ if they are cheating liars. If we can definitively prove that statement $-B$ is false, then (correct me if I'm wrong) both statement A and statement B are true.

Students $4n$ are the easiest fish to bait. Assume that there is a non-empty set $U$ of students $4n$ who are cheating. Of course, every non-empty set has a first member, so let $n$ be the first member of this set such that $4n$ is cheating. This means that all $4m$ before $4n$ are truthful.

Let $m$ be a number that's approximately 'half' that of $n$. If $n$ is even, we can have $m = \frac{n}{2}$. If $n$ is odd, we can have $m = \frac{n-1}{2}$. As student $4m$ is truthful, $C(4m) \leq 2m + 1$ and $C(8m + 1) - C(4m + 1) \leq 2m + 1$ are both satisfied. We can consider these cases separately.

Firstly for even $n$. Even numbers reduce to $C(2n) \leq n+1$ and $C(4n + 1) - C(2n + 1) \leq n+1$. We also have $C(4n + 1) = C(4n) + 1$ and $C(2n + 1) = C(2n)$; so making the substitutions and adding the equations together gives $C(4n) \leq 2n + 1$, which contradicts our original assumption.

For odd $n$, we can do a similar thing, leading to $C(4n-3) \leq 2n$, which implies $C(4n-2) \leq 2n+1$. Now is where things get much more complicated. We know that $C(4n) > 2n + 1$, so there either student $4n-2$ or student $4n-1$ (or both) have to be cheaters.

If Student $4n-2 = 4(n-1)+2$ is cheating, he saw less than $2n$ people, but since $C(4n) > 2n + 1$, $C(4n - 2)$ has to be greater than $2n$, which is a contradiction. Therefore it is impossible for $C(4n-2)$ to be $2n$ (if $C(4n-2) = 2n$, then students $4n-2$ and $4n-1$ would both have to be cheating).

Then it must be $2n+1$. Then, we invoke that since all students that are multiples of $4$ before this are truthful, then $C(4n - 4) \leq 2n - 1$. But since $4n-4$ is truthful, $C(4n-4) = C(4n-3)$. Immediately we get $C(4n-3) \leq 2n-1$ and $C(4n-2) > 2n$, which are obviously contradictory.

There are edge cases for students $0$ and $4$, but it is easy to manually prove they are non-cheaters (see the chart below).

Now, we see that there is no first element of $U$. The only set there is that has no first element is the empty set! Therefore, $C(4n)$ must always be non-cheaters and telling the truth. So we get the answer to your first challenge: Student 20 is truthful.

Then, we can attempt to do the same:

for $4n + 1$, $4n + 2$, and $4n + 3$, assuming they cheated. Unfortunately, $4n+1$ and $4n+3$, in the long run, don't return anything useful that can be used to make a contradiction. $4n + 2$ is interesting, but we can't use the same method as $4n$ because there's a greater sign instead of a less sign. I believe since there's so many unknowns, the situation is not contradictory.

More information:

We have $C(4 \cdot 2^n) \leq 2(2^n + 1) + \sum_{k=0}^{n} c(4 \cdot 2^k + 1)$.

Here we have a table from 0 to 8:

Student	0	1	2	3	4	5	6	7	8
$c(n)$	0	1	0	0	0	?	?	?	0
$C(n)$	0	0	1	1	1	?	?	?	between 1 and 3