ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 79290
Темы:    [ Замощения костями домино и плитками ]
[ Вспомогательная раскраска ]
[ Процессы и операции ]
[ Индукция (прочее) ]
Сложность: 6+
Классы: 9,10,11
В корзину
Прислать комментарий

Условие

Прямоугольный лист бумаги размером a×b см разрезан на прямоугольные полоски, каждая из которых имеет сторону 1 см. Линии разрезов параллельны сторонам исходного листа. Доказать, что хотя бы одно из чисел a или b целое.

Решение

Назовём прямоугольную полоску, являющуюся элементом указанного разбиения, блоком. Обозначим одну из сторон исходного прямоугольника длины b через B; назовем блок горизонтальным, если его единичная сторона параллельна стороне B, и вертикальным — в противном случае. Обозначим прямую, параллельную B, отстоящую от B на расстояние x и пересекающую данный прямоугольник, через Lx (тогда xa). Будем считать, что прямая B — левая.
Если вертикальный блок расположен между прямыми Li и Li + 1 для некоторого целого i, то выкрасим его в красный цвет, остальные вертикальные блоки выкрасим в синий цвет, а все горизонтальные — в жёлтый. Сумму длин красных отрезков прямой Lx обозначим через К(Lx) синих — через С(Lx) и жёлтых — через Ж(Lx). (Если отрезок разделяет блоки двух цветов, будем считать, что он имеет цвет правого блока.) Очевидно, что Ж(Lx) — целое число для любого x. Покажем, что если перекрасить все синие блоки в жёлтый цвет, то сумма длин жёлтых частей любой прямой Lx останется числом целым. Для этого нам достаточно доказать, что сумма длин синих частей прямой Lx (то есть С(Lx)) — целое число при любом x.
Обозначим всевозможные расстояния от синих блоков до B через α1, α2, ..., αn, причём

0 < α1 < α2 < ... < αna − 1.

Прежде всего, покажем, что можно перекрасить блоки C1(1), ..., Сk1(1), отстоящие от B на расстояние α1. Пусть [a] — целая часть числа a. Так как α1 — наименьшее среди всех расстояний от синих блоков до прямой B и [α1] < α1, то К(Lα1) = К(L1]) = b − Ж(Lα1). Поэтому С(Lα1) = b − К(Lα1) − Ж(Lα1) = Ж(L1]) − Ж(Lα1) — целое число, и, значит, блоки C1(1), ..., Сk1(1) можно перекрасить, поскольку произвольная прямая Lx либо пересекает их все, либо не пересекает ни одного из них.
Точно так же доказывается, что из возможности перекрасить блоки C1(s), ..., Сk1(s), отстоящие от B на расстояние as для всех si − 1 следует, что можно перекрасить блоки C1(i), ..., Сk1(i). Теперь утверждение следует из принципа математической индукции: C(Lx) — целое при любом x. Итак, у нас остались лишь красные и жёлтые блоки. Если теперь прямая L[a] совпадает со стороной прямоугольника, то a — целое число. Если же нет, то

b = Ж(L[a]+ε), [a] + ε < a,

и так как Ж(Lx) — целое, то, значит, и b — целое. Утверждение полностью доказано.

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

олимпиада
Название Московская математическая олимпиада
год
Номер 37
Год 1974
вариант
Класс 9
Тур 2
задача
Номер 5
олимпиада
Название Московская математическая олимпиада
год
Номер 37
Год 1974
вариант
Класс 10
Тур 2
задача
Номер 5
журнал
Название "Квант"
год
Год 1974
выпуск
Номер 9
Задача
Номер М285

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .