Начало
Помощь
Поиск
Войти
Регистрация
Добро пожаловать,
Гость
. Пожалуйста,
войдите
или
зарегистрируйтесь
.
Войти
Логические задачи
NazVa.net
Форум умных людей
>
Задачи и головоломки
>
Помогите решить!
(Модераторы:
Илья
,
Лев
) >
Помогите решить!
Страниц: [
1
]
« предыдущая тема
следующая тема »
Печать
Автор
Тема: Помогите решить! (Прочитано 2282 раз)
0 Пользователей и 1 Гость смотрят эту тему.
logic
Новенький
Offline
Сообщений: 3
СПАСИБО
-вы поблагодарили: 0
-вас поблагодарили: 0
Помогите решить!
�
:
Июнь 25, 2012, 12:07:57 �
Имеется n натуральных чисел a1, ..., an, где a1=1, a2<=2, an<=n (ai > 0), и их сумма составляет четное число. Докажите, что можем разделить это множество на 2 части с одинаковой суммой.
Записан
Um_nik
Гений-Говорун
Offline
Сообщений: 1161
СПАСИБО
-вы поблагодарили: 277
-вас поблагодарили:
341
Любовь - дело техники
Re: Помогите решить!
�
Ответ #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
]
Печать
« предыдущая тема
следующая тема »
Перейти в:
Пожалуйста, выберите назначение:
-----------------------------
Задачи и головоломки
-----------------------------
=> Логические задачи и головоломки
=> Математические задачи
=> Задачи на знания
=> Задачи по настольным играм
=> Для программистов
=> Авторские задачи
=> Помогите решить!
=> Назва Продуксьон
=> Тесты
=> Умное видео
=> Игры
-----------------------------
Общение
-----------------------------
=> Отдых, развлечения, увлечения
=> Общество
=> Любовь
=> Философский
=> Свободное общение
-----------------------------
Nazva.net
-----------------------------
=> Сайт
-----------------------------
Trash
-----------------------------
=> Реклама