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

Решение:

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

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

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

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

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

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

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

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