ЗАДАЧА С ИСТОРИЕЙ
Задача о разбиении прямоугольника на полоски
А.КЛИМОВ
НА МОСКОВСКОЙ МАТЕМАТИЧЕСкой олимпиаде 1974 года в двух старших классах была предложена следующая задача. Прямоугольный лист бумаги размером a u b см разрезан на прямоугольные полоски, каждая из которых имеет сторону 1 см. Линии разрезов параллельны сторонам исходного листа. Докажите, что хотя бы одно из целое. Интересна история ее появления. Сначала сделаем небольшое отступление об обстоятельствах жизни тех лет. Тогда в Москве сносили много старых зданий, в которых много чего было ценного с точки зрения искусства. У Коли (хорошо известного в олимпиадных кругах) был друг (вроде даже одноклассник) – художник Витя Галкин. Он был одержим идеей спасения и сохранения того ценного, что было в этих разрушаемых домах. Это не только предметы (как светильники или самовары), но также детали мебели и самих зданий – ручки, балясины, подоконники, панно и много чего еще. Коля ему содействовал, вдохновляя нас, студентов, в этом участвовать. Когда становилось известно, что через день-два будут разрушать какой-то замечательный дом, мы туда приезжали, иногда ночью, чтобы все, что еще оставалось ценного, вывинчивать, отрывать, выдирать и грузить на машину. У Вити был довольно большой дом в деревне Грызлово, расположенной у реки Лопасня. В этом доме мы и складировали «добычу». А потом мы помогали ему все это сортировать и приводить в порядок.
1 Николай Николаевич Константинов – вы-
дающийся организатор математического образования. Читайте интервью с ним в «Кванте» №1 за 2010 год.
И вот как-то раз мне пришлось заняться кучей мелких квадратных плиток единого размера примерно 2 u 2 см. Надо было их поплотнее упаковать в деревянную коробку с размерами, разумеется, не кратными стороне плитки. Причем плитки были самой разной толщины – от 3 до 8 мм. Поэтому я решил ставить их на ребро в один слой, чтобы потом на них положить второй слой и т.д. Заканчивая слой, я увидел, что остается незаполненный кусочек, причем такой площади, что еще 1–2 плитки туда бы вошли. Я стал пытаться менять ориентацию плиток, но все было тщетно. Пришлось оставлять пустое место. И только на другой день, уже в Москве, я понял, что в этом скрыт некий математический факт. Так и появилась приведенная выше задача. Причем меня еще, конечно, интересовала минимальная площадь остатка при заданных нецелых a и b. Предстояла очередная олимпиада, и это была бы хорошая задача для нее. Однако решить задачу долго не получалось. Наконец нашлось решение, довольно сложное, под которое ее были согласны принять. Я надеялся, что кто-то из участников сможет найти более простое решение. Но это ожидание не сбылось. Задачу дали в двух старших классах, 9 и 10. И насколько я помню, было лишь 2 или 3 работы, в которых можно было с большой натяжкой разглядеть прототип возможного доказательства. В одной из этих работ – ее писал Андрей Коробов из 10 класса 179-й математической школы – был набросок доказательства для случая, когда обе стороны листа рациональные, т.е. точно кратные 1 n для некоторого целого n. Размеры полосок тоже предполагались рациональными. Также предполагалось, что все разрезы идут по линиям сетки с шагом 1 n. Были закрашены клетки на диагоналях, проведенных в исходном прямоугольнике с шагом в n клеток (т.е. 1 см). Получалось, что в каждой элементарной полоске размера 1 u n клеток имеется ровно 1 закрашенная клетка при любом ее положении или любой ориентации. Поэтому в каждой полоске размера m u n (клеток) содержится ровно m закрашенных клеток, т.е. их количество строго пропорционально общему числу клеток в ней mn. Теперь оставалось убедиться, что если обе стороны исходного листа не кратны n (в смысле числа клеток),
24
КВ А НT 2024/№10
то для площади всего листа эта пропорциональность не соблюдается. Все, что теперь мне оставалось, – это как бы перейти к пределу при n o f и получить следующее элементарное (т.е. школьное, без бесконечностей) решение для Будем решать задачу в более широкой постановке. Рассматривая любые неполные покрытия листа a u b без наложений прямоугольными полосками ширины 1 со сторонами, параллельными сторонам листа, докажем, что оба не целые, то всегда будет оставаться непокрытая часть листа. Также попытаемся оценить снизу размер остатка в зависимости Нанесем на исходный лист серию диагональных (под 45q к стороне) прямых линий одного направления (голубых линий на рисунке), отстоящих друг от друга на 1 см по
^ a ^ b меньше (или равна) 1, то ни одного
фрагмента секущей он не содержит, поскольку угол листа лежит ниже диагонали дополненного единичного квадрата (показанного пунктиром). В итоге отрезанными полосками покрыты все секущие, а значит, их суммарная площадь равна L. И если даже в этом случае остается непокрытым кусок площади ^ a ^ b, то и при любом другом покрытии останется не меньше. Далее, если ^ a ^ b! 1, то длина проекции секущей в этом прямоугольничке будет ^ a ^ b 1, поэтому остаточная площадь при любом покрытии составит как минимум
^ a ^ b ^ a ^ b 1
1 ^ a 1 ^ b! 0.
Таким образом, мы нашли нижнюю границу площади непокрытой части листа:
min ^ a ^ b, 1 ^ a 1 ^ b.
вертикали и по горизонтали. Будем называть их секущими. Всякая полоска размера 1 u l накрывает фрагменты секущих суммарной длины l 2 или если измерять длины фрагментов по их проекциям на Тем самым, эта условная «длина» равна площади полоски. (Действительно, ведь эти проекции точно покрывают без перекрытий.) Пусть L – сумма «длин» всех секущих на листе. При любом покрытии суммарная площадь полосок не может быть больше L. Пусть одна из секущих проходит через левый нижний угол листа, как на рисунке. Рассмотрим следующую эталонную нарезкупокрытие. Отрежем полные (от края до края) полоски ширины 1 слева по максимуму, а потом короткие полоски высоты 1 снизу, как показано на рисунке. Они покрывают весь лист за исключением небольшого прямоугольника справа вверху размера ^ a u ^ b. Здесь ^ x ` – дробная часть Если сумма сторон этого прямоугольника
Это число, очевидно, больше оба не целые. При этом, когда ^ a ^ b 1, минимальным является первый аргумент минимума и наоборот. Возникает вопрос, а достигается ли полученная нижняя граница при ^ a ^ b! 1? Если одна из сторон листа меньше 1, то отрезать полоску шириной 1 можно только по другой стороне (если она больше 1), и потому остаток будет всегда ^ a ^ b. Но если обе стороны больше 1, то граница 1 ^ a 1 ^ b достижима. Предоставляем читателю найти соответствующую нарезку самому (например, когда 1 a, b 2 и a b! 3 ).