Квадрат 100 × 100 разбит на квадраты 2 × 2. Потом его разбивают на доминошки (прямоугольники 1 × 2 и 2 × 1).
Какое наименьшее количество доминошек могло оказаться внутри квадратов разбиения?
1 Ответ
Решение.
Пример. Верхнюю и нижнюю горизонтали разобьем на горизонтальные доминошки — они окажутся в квадратах 2×2. Остальной прямоугольник 98×100 разобьём на вертикальные доминошки — они не окажутся в квадратах 2 × 2. Оценка. Рассмотрим квадраты A1, A3, . . . , A99 размеров 1 × 1, 3 × 3, . . . , 99 × 99, у которых левый нижний угол совпадает с левым нижним углом исходного квадрата 100 × 100. Для каждого из квадратов Ai (i = 1, 3, 5, . . . , 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.