Задача 116498

Темы:    [ Шахматная раскраска ] [ Примеры и контрпримеры. Конструкции ] [ Симметрия помогает решить задачу ]

Сложность: 3+ Классы: 10,11

Условие

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

Решение

  Выделим 20 белых клеток (на рис.они помечены знаком "×").

  Любая чёрная клетка соседствует не более чем двумя выделенными белыми. Поэтому, чтобы обеспечить хотя бы эти белые клетки отмеченными соседями, потребуется отметить не менее десяти чёрных клеток. Аналогично придётся отметить не менее десяти белых клеток. Таким образом, на доске необходимо отметить не менее двадцати клеток.
  Пример двадцати отмеченных клеток, удовлетворяющих условию см. в задаче 103868.

Ответ

20 клеток.

Замечания

Для доски n×n эта задача предлагалась на Международной математической олимпиаде 1999 г.

Источники и прецеденты использования

олимпиада
Название	Окружная олимпиада (Москва)
год
Год	2011
Класс
Класс	11
Задача
Номер	11.6