Форум умных людей

Имеется n натуральных чисел a1, ..., an, где a1=1, a2<=2, an<=n (ai > 0), и их сумма составляет четное число. Докажите, что можем разделить это множество на 2 части с одинаковой суммой.

Начинаем распределять с n-ного к первому. n-ное число определим в первую группу. Тогда разница между суммами групп не более n. Теперь каждое следующее числа будем определять в ту группу, в которой сумма не больше суммы другой группы. Предположим, что после i-ого числа разность сумм групп не превышает i. Тогда после (i-1)-ого разность не будет превышать (i-1). В самом деле: Если разница осталась в ту же сторону, то она уменьшилась, т.к. (i-1)-ое число не меньше 1; Если разница стала в другую сторону, то она не более (i-1), т.к. (i-1)-ое число не более (i-1). Т.к. для i=n наше предположение справедливо, оно (по индукции) справедливо для всех i, в том числе для i=1.
Разность сумм групп не превышает единицу. Предположим, что она равна 1. Тогда суммы групп имеют разную четность, и сумма всех чисел - число нечетное. Но это противоречит условию => суммы групп равны.
ч.т.д.