Задача 109572

Темы:    [ Геометрия на клетчатой бумаге ] [ Покрытия ] [ Индукция в геометрии ]

Сложность: 4+ Классы: 8,9,10

Условие

Автор: Перлин А.

Плоскость разбита двумя семействами параллельных прямых на единичные квадратики. Назовем каемкой квадрата n ×n, состоящего из квадратиков разбиения, объединение тех квадратиков, которые хотя бы одной из своих сторон примыкают изнутри к его границе. Докажите, что существует ровно один способ покрытия квадрата 100×100 , состоящего из квадратиков разбиения, неперекрывающимися каемками пятидесяти квадратов. (Каемки могут и не содержаться в квадрате 100× 100 .)

Решение

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

Источники и прецеденты использования

олимпиада
Название	Всероссийская олимпиада по математике
год
Год	1994
Этап
Вариант	5
класс
Класс	9
задача
Номер	94.5.9.8