Question

Дан квадрат размером 35×35 клеток. Какое минимальное количество клеток нужно закрасить, чтобы из любой не закрашенной клетки нельзя было попасть в не закрашенную ходом шахматного коня?​

Answer 1

Рассмотрим пример попроще, вместо 35х35 будет квадрат 7х7. Если брать клетки в шахматном порядке и закрашивать все, в которые можно попасть ходом коня, то получится такая картина (смотреть вложение). Значит, для таблицы размером 35х35 все будет аналогично, ведь она просто в 25 раз больше.

Теперь посчитаем количество клеток. В случае с таблицей 7х7 есть два варианта: 3*4+4*3 = 24 или 4*4 + 3*3 = 25. Нам нужен первый вариант

Для таблицы 35x35 будет 17*18 + 18*17 = 612

Ответ: 612