Задача
ALG-B2-M01-P027 Разбиение на две группы
Даны \(101\) ненулевых целых чисел. Для каждого числа сумма этого числа и произведения всех остальных чисел отрицательна. Докажите, что при любом разбиении чисел на две непустые группы сумма произведений чисел в этих двух группах отрицательна.
Подсказка 1. Сначала определите чётность числа отрицательных элементов.
Подсказка 2. В отрицательной группе выделите один отрицательный множитель.
Если отрицательных чисел было бы чётное количество, то нашлось бы положительное число \(a\), а произведение всех остальных было бы положительным. Тогда \(a+\prod_{\ne a}>0\), противоречие. Значит, отрицательных чисел нечётное количество.
Разобьём числа на две группы. Тогда ровно одно из двух произведений отрицательно. Пусть \(X=x_1x_2\cdots x_r<0\), \(Y=y_1y_2\cdots y_s>0\), и пусть \(x_1<0\). Тогда \(x_2\cdots x_r>0\), а так как числа целые, \(x_2\cdots x_r\ge1\). Поэтому \[X+Y=x_1(x_2\cdots x_r)+Y\le x_1+Y\le x_1+Y(x_2\cdots x_r).\] Последнее выражение отрицательно по условию, применённому к числу \(x_1\). Значит, \(X+Y<0\).
A. Анализ источника. Главные объекты: неравенства, порядок, экстремальный элемент или инвариант. Очевидный первый ход обычно даёт только локальную оценку. Скрытое наблюдение: надо выбрать правильную величину, которая не может уменьшаться, либо перемножить/сложить неравенства только после проверки знаков. Нужный шаг: переход к упорядоченной записи, инварианту, произведению или граничному случаю.
F. Обоснование сложности. Региональный уровень 7: два ключевых шага — чётность знаков и использование целочисленности для оценки произведения.
G. Почему это не одноходовая задача. Недостаточно знать знак общего произведения; нужно оценить любое разбиение.