11
$\begingroup$

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.
$\endgroup$
2
  • 3
    $\begingroup$ Love these problems! I hope this becomes a full-blown series $\endgroup$ Jul 11 at 16:02
  • $\begingroup$ That’s the hope! As long as I can keep thinking of new ideas! $\endgroup$ Jul 11 at 16:03

1 Answer 1

4
$\begingroup$

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
$\endgroup$
7
  • $\begingroup$ rot13("V oryvrir gurer ner ner fbzr reebef jvgu gur terngre guna/yrff guna fvtaf, ohg, bapr lbh znxr gur pbeerpgvbaf, lbhe zrgubq jvyy fgvyy jbex gb cebir gung $4a$ qvqa'g purng, jvgu n srj fznyy nqwhfgzragf. Va cnegvphyne, lbhe pynvz gung $P(o) - P(n) < o - n$ vf ershgrq ol frggvat $n = 0$ naq $o = 1$. Nyfb, fbzr bs gur fgngrzragf va gur svefg fcbvyre obk unir gur fvtaf cbvagvat va gur jebat qverpgvba.") $\endgroup$ Jul 12 at 1:06
  • 1
    $\begingroup$ @GavinDooley Oops, my bad. Turns out writing haphazardly does not have a positive effect on neatness $\endgroup$ Jul 12 at 1:26
  • $\begingroup$ @GavinDooley I actually completely changed my proof because my original method was somewhat flawed $\endgroup$ Jul 12 at 16:32
  • $\begingroup$ Hi @new Q Open Wid! Very sorry for the late response! I was busy and I didn't have a chance to look through your revision. Your solution is impressive and very close, but with a small error. $\endgroup$ Jul 26 at 16:22
  • $\begingroup$ rot13("Lbh znxr na reebe jura lbh fnl 'Nf fghqrag 4z vf gehgushy, P(4z)≤2z+1 naq P(8z+1)−P(4z+1)≤2z+1 ner obgu fngvfsvrq.' Gur snpg gung 4z vf gehgushy qbrf abg gryy hf nalguvat nobhg P(4z). Guvf vf orpnhfr 4z vf snpvat njnl sebz gur obneq naq gurve fgngrzrag pnaabg erirny nalguvat nobhg fghqragf jvgu ybjre ahzoref. Ubjrire, lbh pna nqwhfg lbhe nethzrag gb znxr vg jbex. Va cnegvphyne, lbh fubhyq fgeratgura lbhe vaqhpgvir ulcbgurfvf nf sbyybjf: Vafgrnq bs yrggvat a or gur yrnfg a fhpu gung Fghqrag 4a purngrq, yrg a or gur yrnfg a fhpu gung P(4a) > 2a+1.") $\endgroup$ Jul 26 at 16:24

Your Answer

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

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