Задача 109441

Темы:    [ Принцип Дирихле (прочее) ] [ Задачи с ограничениями ]

Сложность: 4 Классы: 8,9,10,11

Условие

Даны таблица 100×100 клеток и N фишек. Рассматриваются все такие расстановки фишек в клетки таблицы, что никакие две фишки не стоят в соседних клетках. При каком наибольшем N в каждой из этих расстановок можно найти хотя бы одну фишку, от перемещения которой в соседнюю клетку заданное условие не нарушится? (Соседними считаются клетки, имеющие общую сторону.)

Решение

  Назовём расстановку фишек жёсткой, если перемещение любой фишки в соседнюю клетку нарушает требуемое условие. Жёсткая расстановка из ста фишек существует: поставим все фишки на клетки большой диагонали.
  То, что любая расстановка 99 (или менее) фишек нежёсткая, фактически доказано в задаче 35395.

Ответ

При  N = 99.

Замечания

Имеется в виду, что рассматриваются все расстановки из N и меньшего числа фишек.

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

олимпиада
Название	Окружная олимпиада (Москва)
год
Дата	2007
класс
Класс	11
задача
Номер	7