Задача
ALG-B2-M01-P018 Два множества с малой суммой
Множества \(A\) и \(B\) состоят каждое из \(n\) различных натуральных чисел, причём сумма чисел в каждом множестве равна \(n^2\). Докажите, что \(A\) и \(B\) имеют общий элемент.
Подсказка 1. Предположите, что множества не пересекаются.
Подсказка 2. Тогда объединение содержит \(2n\) различных натуральных чисел.
Предположим, что \(A\cap B=\varnothing\). Тогда \(A\cup B\) содержит \(2n\) различных натуральных чисел, поэтому сумма всех его элементов не меньше \(1+2+\cdots+2n=n(2n+1)\). С другой стороны, эта сумма равна \(n^2+n^2=2n^2\). Но \(n(2n+1)>2n^2\), противоречие. Значит, общий элемент существует.
A. Анализ источника. Главные объекты: неравенства, порядок, экстремальный элемент или инвариант. Очевидный первый ход обычно даёт только локальную оценку. Скрытое наблюдение: надо выбрать правильную величину, которая не может уменьшаться, либо перемножить/сложить неравенства только после проверки знаков. Нужный шаг: переход к упорядоченной записи, инварианту, произведению или граничному случаю.
F. Обоснование сложности. Региональный уровень 6: скрытый шаг — оценить объединение минимальной возможной суммой.
G. Почему это не одноходовая задача. Нельзя сравнивать множества поэлементно; надо перейти к объединению.