Question

Мальвина поставила на шахматную доску 8 на 8 клеток n шашек и велела Буратино поставить на одну из свободных клеток доски шахматного коня, который не бил бы ни одну из шашек. При каком наименьшем n задание может оказаться невыполнимым?

Answer 1

Решение:

Саму задачу можно переформулировать немного по-другому:

• Было: Расставить минимальное количество шашек на шахматной доске 8 на 8, так чтобы было невозможно поставить коня так, чтобы он не бил ни одной шашки.
• Переходит в: расставить на доске минимальное количество коней так, чтобы было невозможно поставить шашку не под удар коня.

Если мы решим вторую задачу, то просто нужно будет заменить коней шашками - и мы получим искомое расположение.

По поводу второй задачи можно заметить, что:

• Разные кони должны бить выделенные красным клетки на рисунке ниже.

Отсюда следует, что мы не можем расставить менее, чем 4 * 3 = 12 коней. Если это можно сделать, то задача решится. И да, это получилось сделать (рисунок 2).

Заменяем коней шашками и получаем ответ: 12 коней.

Ответ: 12 шашек.  

Answer 2

Чтобы найти наименьшее значение n, при котором задание может оказаться невыполнимым, нужно рассмотреть худший сценарий, когда конь не сможет быть поставлен на свободную клетку.

Рассмотрим шахматную доску 8x8. Для коня, чтобы он не бил ни одну из шашек, ему нужно быть размещенным таким образом, что ни одна шашка не находится на одной из 8 клеток, которые бьются конем (это места, куда конь может сделать ход с текущей позиции).

Для каждого из углов доски (4 клетки) конь имеет максимум 2 хода, которые не пересекаются с шашками. Также, для каждой из клеток на краю доски, не являющейся углом (всего 24 таких клетки), конь может иметь максимум 3 хода, которые не пересекаются с шашками.

Таким образом, для оптимального размещения коня нам потребуется 4 свободные клетки для углов и 24 свободные клетки для клеток на краю доски. Всего нам нужно 4 + 24 = 28 свободных клеток.

Если количество шашек (n) больше или равно 28, то разместить коня таким образом, чтобы он не бил ни одну из шашек, будет возможно. Если n меньше 28, задание будет невыполнимым.

Таким образом, наименьшее значение n, при котором задание может оказаться невыполнимым, равно 28. Если на доске 8x8 находится 28 или более шашек, то конь не сможет быть поставлен на свободную клетку без боя с шашками.