Задача
ALG-B2-M01-P030 Избавиться от однородных объектов
В наборе есть прямоугольные карточки с положительными сторонами. Изначально одна карточка имеет обе стороны больше \(1\). Разрешено делать операции: заменить карточку со сторонами \(a,b\) на карточку \(\frac1a,\frac1b\), либо заменить её на две карточки \(c,b\) и \(\frac ac,b\), где \(c>0\). Докажите, что после конечного числа операций невозможно получить набор, в котором у каждой карточки одна сторона больше \(1\), а другая меньше \(1\).
Подсказка 1. Считайте карточки с двумя большими или двумя малыми сторонами.
Подсказка 2. Покажите, что если такая карточка есть, то после операции такая карточка остаётся.
Назовём карточку однородной, если обе её стороны больше \(1\) или обе меньше \(1\). Изначально есть однородная карточка. Если заменить однородную карточку обратной, она остаётся однородной: тип «больше-больше» превращается в «меньше-меньше» и наоборот.
Пусть теперь однородная карточка \((a,b)\) разрезается вторым способом. Если \(a>1,b>1\), то из \(c\cdot\frac ac=a>1\) следует, что хотя бы одно из \(c,\frac ac\) больше \(1\); соответствующая новая карточка вместе с \(b>1\) однородна. Если \(a<1,b<1\), то хотя бы одно из \(c,\frac ac\) меньше \(1\), иначе их произведение было бы не меньше \(1\); значит, снова появляется однородная карточка. Поэтому однородные карточки не могут исчезнуть полностью. В требуемом конечном наборе их нет, противоречие.
A. Анализ источника. Главные объекты: неравенства, порядок, экстремальный элемент или инвариант. Очевидный первый ход обычно даёт только локальную оценку. Скрытое наблюдение: надо выбрать правильную величину, которая не может уменьшаться, либо перемножить/сложить неравенства только после проверки знаков. Нужный шаг: переход к упорядоченной записи, инварианту, произведению или граничному случаю.
F. Обоснование сложности. Финальный уровень 8: это инвариантная задача, где объект меняет количество частей.
G. Почему это не одноходовая задача. Здесь невозможно просто отследить площадь; решает классификация объектов.