Даны натуральные числа m и n. Найти такие натуральные числа m₁ и n_1, не имеющие общих делителей, что m₁ / n₁ = m / n.

   Решение

Тема:    [ Замощения костями домино и плитками ]

Сложность: 5 Классы: 8,9

Прислать комментарий

Условие

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

Решение

Докажем это утверждение для любой фигуры, а не только для прямоугольника. Возьмем произвольную карточку A₀. Одна из ее клеток покрыта клеткой другой карточки A₁, вторая клетка A₁ покрыта клеткой карточки A₂ и т. д. Цепочка карточек A₀, A₁, A₂,... замкнется, причем именно на карточке A₀, так как иначе какая-либо клетка будет покрыта трижды (не исключено, что эта цепочка состоит только из двух карточек A₀ и A₁). Замкнутая цепочка карточек состоит из четного числа карточек (для доказательства можно рассмотреть ломаную, каждое звено которой соединяет центры клеток одной карточки; эта ломаная имеет четное число и горизонтальных и вертикальных звеньев). Поэтому для карточек, входящих в замкнутую цепочку, искомым разбиением является разбиение на карточки с четными и нечетными номерами. Все эти карточки выбрасываем и для оставшихся карточек проделываем такую же операцию и т. д.

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