Юля поставила на шахматную доску несколько коней. Затем она посчитала, сколько коней бьёт каждый из них, и из полученных чисел выбрала наименьшее. Какое наибольшее значение может принимать это число?

Для решения этой задачи проанализируем возможности шахматного коня на доске $8 \times 8$.

Дано:

• Шахматная доска $8 \times 8$.
• На доске расставлено $N$ коней.
• Для каждого коня $i$ определено число $k_i$ — количество других коней, которых он бьет.
• Нужно найти максимальное значение $m = \min(k_1, k_2, \dots, k_N)$.

Решение:

1. Анализ углов и краев: Конь, стоящий в углу доски, бьет максимум $2$ поля. Если мы поставим коня в угол, то $k_i \le 2$. Чтобы число $m$ было как можно больше, нам нужно избегать размещения коней в позициях, где они бьют мало полей (углы, края).

2....