Математическая задача про шахматы! ХЕЛП!

Question

Король — шахматная фигура, под боем которой находятся все клетки, соседние с ней по горизонтали, вертикали или диагонали. Вам дана шахматная доска размера 176 на 159 клеток. Какое максимальное количество королей вы сможете разместить на ней так, чтобы никакие два не били друг друга?

Answer 1

У меня вышло 53*59= 3127, хотя далеко неуверен (верне, столько королей можно разместить уверенно; но возможно, и значительно больше) .
Ответы предыдущих товарищей у меня создают впечатление, что они ходы короля не знают. Но, возможно, ошибаюсь.

Answer 2

Ну, давайте покумекаем.
Рассмотрим для начала одномерный случай. Т. е. доску состоящую из одного ряда клеток.
Вариант 1. Чётное количество. На примере двух или четырёх клеток видно, что число королей максимально тупо число клеток делить на два.
Вариант два. Нечётное число. На примере трёх или пяти клеток видно, что макс число равно (число клеток + 1) /2 Король ставиться на крайнюю клетку и дале через одну. Получаем максимальную упаковку. Видно простым перебором.
Всё можно распространить на любое число чёта и нечёта индукцией, но мне немного лень этим заниматься.
Итак для одномерной доски всё понятно. Для двухмерной просто перемножаем результаты по каждому измерению (впрочем так для сколькиугодномерной доски) .

Конкретно в нашем случае (176/2) х (159/2) = 88х80=7040 королей