Бельчонок 2024/25 · Математика · 7 кл., №5 — решение · финал

Условие

Какое наименьшее число клеток нужно отметить на клетчатой доске $18\times18$ так, чтобы фигуркой на рисунке нельзя было накрыть $5$ неотмеченных клеток? Фигурку можно поворачивать и переворачивать.

О задаче · 7 класс · баллы не подтверждены

Олимпиада: Бельчонок
Предмет / класс: Математика · 7 класс
Сезон / этап: 2024/25 · Заключительный этап
Комплект: Вариант 1 · задача 5

Официальные баллыНе подтверждены

Сложность Popov Academy4/5 · предварительно

Для подготовки: 7 класс.

Исследуй задачу

Модель с пояснениями к решениюПостроение по шагам

Есть пояснения и построения из решения. Открой, когда захочешь воспользоваться этой помощью.

От маленького блока к всей доске

Последовательно проверьте форму фигурки, нижнюю оценку и достигающий её узор.

1. Исходная фигурка

Фигурка состоит из четырёх клеток в ряд и одной клетки рядом со второй. Повороты и перевороты разрешены.

Исходная форма сохранена.

2. Сорок блоков

Предположим, что в прямоугольнике $2\times4$ отмечена не более чем одна клетка. Тогда одна из двух длинных строк целиком неотмечена. Сделаем её длинной частью фигурки. Из двух средних клеток соседней строки хотя бы одна неотмечена: выберем её для пятой клетки. Повороты и перевороты фигурки разрешены, поэтому подходят оба положения «ножки». Так фигурка накрывает пять неотмеченных клеток. Значит, чтобы это исключить, в каждом блоке $2\times4$ нужны хотя бы две отметки. В первых $16$ столбцах разобьём строки на $9$ пар, а столбцы — на $4$ группы по четыре. Получим $9\cdot4=36$ блоков $2\times4$ В последних двух столбцах первые $16$ клеток по высоте разобьём на $4$ повёрнутых блока $4\times2$ Все $40$ блоков не пересекаются; внизу справа остаётся квадрат $2\times2$ В каждом блоке необходимы две отметки, поэтому всего их не меньше

40\cdot2=80.

36

горизонтальных и

4

вертикальных блока; четыре серые клетки в нижнем правом углу не участвуют в нижней оценке.

3. Восемьдесят отметок

Пронумеруем строки и столбцы от $0$ до $17$ Отметим клетку, если сумма её номеров даёт остаток $3$ при делении на $4$ В четырёх последовательных клетках любой строки или столбца суммы идут подряд и дают все четыре остатка. Поэтому длинная часть любого положения фигурки обязательно содержит отметку. По строкам число отметок повторяется как $4,4,5,5$ в первых $16$ строках их $4\cdot(4+4+5+5)=72$ а в двух последних ещё $4+4=8$ Всего $80$ отметок.

Отмечены

80

клеток: в любой горизонтальной или вертикальной четвёрке есть ровно одна отметка.

Статичные состояния полностью сопровождают доказательство; менять расположение отметок для его чтения не требуется.

Записать идею

Личный черновик для заметок и расчётов. Он никуда не отправляется и не проверяется.

Подсказка 1

Рассмотрите маленький прямоугольник $2\times4$ Может ли одна отметка помешать всем размещениям фигурки внутри него?

Подсказка 2

Разбейте как можно большую часть доски на непересекающиеся блоки $2\times4$ Для обратной границы используйте диагональный узор с периодом $4$

Разобрать решение по шагам

В блоке 2 на 4 необходимы две отметки

Размещаем сорок непересекающихся блоков

В первых $16$ столбцах разобьём строки на $9$ пар, а столбцы — на $4$ группы по четыре. Получим $9\cdot4=36$ блоков $2\times4$ В последних двух столбцах первые $16$ клеток по высоте разобьём на $4$ повёрнутых блока $4\times2$ Все $40$ блоков не пересекаются; внизу справа остаётся квадрат $2\times2$ В каждом блоке необходимы две отметки, поэтому всего их не меньше

40\cdot2=80.

36

горизонтальных и

4

вертикальных блока; четыре серые клетки в нижнем правом углу не участвуют в нижней оценке.

Строим разметку из восьмидесяти клеток

Отмечены

80

клеток: в любой горизонтальной или вертикальной четвёрке есть ровно одна отметка.

Соединяем обе оценки

Меньше $80$ отметок недостаточно по разбиению на блоки; $80$ достаточно по построенной разметке. Следовательно, искомый минимум равен $80$

Открыть модель к этому разбору ↑

Ответ

$80$ клеток.

Главная идея

Сначала получаем локальную нижнюю границу для блока из восьми клеток, затем суммируем её по непересекающимся блокам и строим достигающий пример.

Как заметить эту идею в другой задаче

Если запрещённую фигурку можно по-разному помещать в маленький прямоугольник, сначала найдите обязательное число отметок в таком прямоугольнике.

Возможная ошибка

Считать достаточную диагональную разметку доказательством минимальности: без нижней оценки это лишь верхняя граница.

Источник и примечания

Официальный источник

PDF организатора · страницы 37 · задача 5 ↗

Бельчонок · 2024/25 · математика · 7 класс · заключительный этап · вариант 1.

Официальное решение · страницы 37 ↗

Авторский разбор прошёл самопроверку, сверку с официальным материалом и отдельную проверку рассуждений ИИ-редактором. Ручная редакторская приёмка ещё не выполнена.

Можете объяснить решение своими словами?

Продолжить тему: Преобразования и разбиения →

Тема, знания и приёмы

Преобразования и разбиения · Продвинутая подготовка

Разбиение доски
Остатки

Приёмы решения: Оценка и достижимость · Раскраска

Задать вопрос по задаче →