Students who see ears of another student

134 Views Asked by At

A student is standing in each cell of an $n\times n$ grid, looking at one of the four directions: up, down, left, right. It turns out that no student is at the border and looking out of the grid, and no student directly sees the face of another student (every student sees either the ear or the back of another student.) What is the minimum number of student who sees the ear?

I think we can achieve $n+4$ with this configuration, shown for $n=5$. (The arrows show which way the students are facing.)

$$\begin{matrix} \downarrow&\downarrow&\downarrow&\downarrow&\downarrow\\ \downarrow&\downarrow&\downarrow&\downarrow&\downarrow\\ \downarrow&\downarrow&\downarrow&\downarrow&\downarrow\\ \downarrow&\downarrow&\downarrow&\rightarrow&\downarrow\\ \rightarrow&\rightarrow&\rightarrow&\uparrow&\leftarrow \end{matrix}$$

2

There are 2 best solutions below

2
On BEST ANSWER

The minimum is $n+2$, with the construction in chubakueno's comment.

Proof that this is minimal:

Split the students into lines (maximal subsets of students in a straight line all looking the same direction).

The last student in each line must be looking at an ear (in fact, the number of lines equals the number of students looking at an ear).

Each line has at most $n-1$ students.

Thus there are at least $\lceil \frac{n^2}{n-1} \rceil = n+2$ lines, and thus at least this many students looking at an ear.

An illustration (slight modification of chubakueno's comment):

$$\begin{matrix} \downarrow&\downarrow&\downarrow&\downarrow&\leftarrow\\ \downarrow&\downarrow&\downarrow&\downarrow&\uparrow\\ \downarrow&\downarrow&\downarrow&\downarrow&\uparrow\\ \downarrow&\downarrow&\downarrow&\downarrow&\uparrow\\ \rightarrow&\rightarrow&\rightarrow&\rightarrow&\uparrow \end{matrix}$$

You see $n+1$ lines each with the maximum $n-1$ elements, plus one lonely student in a line of one element (upper right).

3
On

Consider a slight modification of your arrangement: $$\begin{matrix} \downarrow&\downarrow&\downarrow&\downarrow&\downarrow\\ \downarrow&\downarrow&\downarrow&\downarrow&\downarrow\\ \downarrow&\downarrow&\downarrow&\downarrow&\color{red}\downarrow\\ \color{red}\downarrow&\color{red}\downarrow&\color{red}\downarrow&\color{red}\downarrow&\color{red}\leftarrow\\ \rightarrow&\rightarrow&\rightarrow&\color{red}\rightarrow&\color{red}\uparrow \end{matrix}$$ which looks better to me, and in the general case, gives $n+3$ as the number of students who see the side of another student's face for $n \ge 3$, and for $n = 2$, the minimum is obviously $4$.