ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 116498
Темы:    [ Шахматная раскраска ]
[ Примеры и контрпримеры. Конструкции ]
[ Симметрия помогает решить задачу ]
Сложность: 3+
Классы: 10,11
В корзину
Прислать комментарий

Условие

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


Решение

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

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


Ответ

20 клеток.

Замечания

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

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

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

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .