Problem 6.3. A country has the shape of a square and is divided into 25 identical square counties. In each county, either a knight-count, who always tells the truth, or a liar-count, who always lies, rules. One day, each count said: "Among my neighbors, there are an equal number of knights and liars." What is the maximum number of knights that could have been? (Counts are neighbors if their counties share a common side.)
Answer: 8.

Solution. First, note that counties with exactly three neighboring counties must be governed by lying counts (Fig. ??). Therefore, the corner counties are also governed by liars, since both of their neighbors are liars.

|  | $L$ | $L$ | $L$ |  |
| :--- | :--- | :--- | :--- | :--- |
| $L$ |  |  |  | $L$ |
| $L$ |  |  |  | $L$ |
| $L$ |  |  |  | $L$ |
|  | $L$ | $L$ | $L$ |  |

Fig. 1: to the solution of problem $? ?$

It remains to figure out the central $3 \times 3$ square. All cells cannot be occupied by knights, since then the central knight would have all neighbors as knights. Therefore, there are no more than 8 knights. An example with eight knights is shown in Fig. ??.

|  |  |  |  |  |
| :--- | :--- | :--- | :--- | :--- |
|  | $\mathrm{P}$ | $\mathrm{P}$ | $\mathrm{P}$ |  |
|  | $\mathrm{P}$ |  | $\mathrm{P}$ |  |
|  | $\mathrm{P}$ | $\mathrm{P}$ | $\mathrm{P}$ |  |
|  |  |  |  |  |

Fig. 2: to the solution of problem $?$ ?

## Criteria

Any correct solution to the problem is worth 7 points. In the absence of such a solution, the following criteria are summed:

4 6. It is proven that knights can only be in the central $3 \times 3$ square.