Олимпиадная задача по комбинаторике для 8–11 класса: максимальное размещение фишек на таблице 100×100
Задача
Даны таблица 100×100 клеток и N фишек. Рассматриваются все такие расстановки фишек в клетки таблицы, что никакие две фишки не стоят в соседних клетках. При каком наибольшем N в каждой из этих расстановок можно найти хотя бы одну фишку, от перемещения которой в соседнюю клетку заданное условие не нарушится? (Соседними считаются клетки, имеющие общую сторону.)
Решение
Назовём расстановку фишек жёсткой, если перемещение любой фишки в соседнюю клетку нарушает требуемое условие. Жёсткая расстановка из ста фишек существует: поставим все фишки на клетки большой диагонали.
То, что любая расстановка 99 (или менее) фишек нежёсткая, фактически доказано в задаче 135395.
Ответ
При N = 99.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь
Комментариев нет