Решение задачи 158

Условие:

Какое наименьшее число королей нужно поставить на шахматную доску так, чтобы они били все клетки доски? (король бьет клетку на которой стоит)

Решение:

Отметим некоторые клетки доски звездочкой:

Очевидно, что никакой король не может бить сразу две клетки, отмеченные звездочкой. Значит потребуется минимум 9 королей хотя бы для того, чтобы клетки, отмеченные звездочкой, находились под боем. Нетрудно видеть, что если поставить 9 королей на клетки, отмеченные звездочкой, то они будут бить всю доску.

Ответ: 9.