Тема Закл (финал) 10 класс

Закл 2023

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела закл (финал) 10 класс

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#128454

Квадрат $100×100$ разбит на квадраты $2× 2.$ Потом его разбивают на доминошки (прямоугольники $1 ×2$ и $2× 1).$ Какое наименьшее количество доминошек могло оказаться внутри квадратов разбиения?

Источники: ВСОШ, ЗЭ, 2023, 10.6 (см. olympiads.mccme.ru)

Показать ответ и решение

Пример. Верхнюю и нижнюю горизонтали разобьём на горизонтальные доминошки — они окажутся в квадратах $2×2.$ Остальной прямоугольник $98× 100$ разобьём на вертикальные доминошки — они не окажутся в квадратах $2 ×2.$

Оценка. Рассмотрим квадраты $A1,$ $A3,...,A99$ размеров $1× 1,$ $3× 3,...,99× 99,$ у которых левый нижний угол совпадает с левым нижним углом исходного квадрата $100 ×100.$ Для каждого из квадратов $Ai$ $(i= 1,3,...,99)$ найдётся доминошка $Xi,$ пересекающая его сторону (поскольку квадраты нечётной площади не разбиваются на доминошки). Легко видеть, что $Xi$ лежит внутри квадратика $2× 2$ из разбиения. Аналогично, рассматривая квадраты $B1,B3,...,B99$ размеров $1×1,$ $3× 3,...,99× 99,$ у которых правый верхний угол совпадает с правым верхним углом исходного квадрата $100× 100,$ находим ещё $50$ нужных нам доминошек $Yj$ ( $j = 1,3,5,...,99).$ Это завершает решение (очевидно, что все доминошки $X1,$ $X3,...,X99,$ $Y1,$ $Y3,...,Y99$ различны).

Ответ:

100