Олимпиадная задача по комбинаторной геометрии и индукции для 8-10 классов: покрытие квадрата каемками
Задача
Плоскость разбита двумя семействами параллельных прямых на единичные квадратики. Назовем каемкой квадратаn×n, состоящего из квадратиков разбиения, объединение тех квадратиков, которые хотя бы одной из своих сторон примыкают изнутри к его границе. Докажите, что существует ровно один способ покрытия квадрата100×100, состоящего из квадратиков разбиения, неперекрывающимися каемками пятидесяти квадратов. (Каемки могут и не содержаться в квадрате100× 100.)
Решение
Для каждой каемки проведем две вертикальных и две горизонтальных полоски шириной 1, в которых лежат ее клетки. Тогда проведенные полоски покрывают наш квадрат, поэтому либо все 100 горизонтальных, либо все 100 вертикальных полосок, пересекающих квадрат, проведены (пусть это вертикальные). Таким образом, все вертикальные полоски для разных каемок не совпадают и проходят по клеткам квадрата.
Отсюда следует, что две угловые клетки квадрата (скажем, A и B ) покрыты одной и той же каемкой, и остальные две угловые клетки ( C и D ) также покрыты одной каемкой. Сторона каждой из этих каемок не меньше 100; однако для каждой из этих каемок обе вертикальные полоски пересекают квадрат. Поэтому это одна и та же каемка со стороной 100, содержащая все граничные клетки нашего квадрата. Удалив эту каемку, мы получим квадрат98x 98, к которому можно снова применить аналогичные рассуждения. Продолжая эту процедуру, мы убедимся, что утверждение задачи справедливо.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь