Страниц: [1]
  Печать  
Автор Тема: Помогите решить!  (Прочитано 1817 раз)
0 Пользователей и 1 Гость смотрят эту тему.
logic
Новенький
*
Offline Offline

Сообщений: 3

СПАСИБО
-вы поблагодарили: 0
-вас поблагодарили: 0


Просмотр профиля
: Июнь 25, 2012, 12:07:57 �

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

Сообщений: 1161

СПАСИБО
-вы поблагодарили: 277
-вас поблагодарили: 341


Любовь - дело техники

623784586
Просмотр профиля Email
Ответ #1 : Июнь 25, 2012, 18:32:07 �

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

"за полчаса до смерти..."
Показать скрытый текст
//текст доступен после регистрации//
Страниц: [1]
  Печать  
 
Перейти в: