An interesting problem as we approach final exams in some places of the world.
Suppose a classroom has the desks arranged in a 5x4 array. There are 18 students. What is the minimal number of exam versions (same exam but in a different order) such that a student is not adjacent vertically, horizontally or diagonally to their exam version?
My thought is that it must that the minimal number of exams is 4. Can you provide a scalable proof or argument?
On
Consider the function $f(x, y) = (x \bmod 2, y \bmod 2)$. Since every location adjacent to $(x, y)$ changes at least one of $x$ and $y$ by $1$, the value of $f$ is different on adjacent vertices. Since $f$ only takes the $4$ values in $\{0, 1\}^2$, this is a solution with at most $4$ exams.
It is possible for there to be a solution with fewer exams if the number of students is small enough compared to the size of the array. For example, removing $f^{-1}(0, 0)$ (and indexing starting at $1$), you can place $mn - \lfloor m/2 \rfloor \lfloor n/2\rfloor$ students in an $m \times n$ array of desks and have a solution with $3$ exams. On the other hand, if there is a solution with $3$ exams, then at least one desk in every $2 \times 2$ must be empty, so this is also an upper bound. For $m = 5$, $n = 4$, you get the bound $20 - 4 = 16$, so to place $18$ students you need at least $4$ exams no matter which arrangement.
By similar arguments, the maximum number of students that can be arranged in some way is $\max(m \lceil n/2 \rceil, n \lceil m/2 \rceil)$ for $2$ exams and $\lceil m/2\rceil \lceil n/2\rceil$ for just $1$ exam (ie no two students are adjacent).
The maximum is 4. The proof is vertex coloration for planar graphs. A Lowerbound is definitly 3 as the graph has necessarily triangles. If you manage to arrange the students such that there is no clique of size 4 you may only need 3 exams, and such an arrangement is a sufficient proof