Задача
Дано n целых чисел a1 = 1, a2, a3, ..., an, причём ai ≤ ai+1 ≤ 2ai (i = 1, 2,..., n – 1) и сумма всех чисел чётна. Можно ли эти числа разбить на две группы так, чтобы суммы чисел в этих группах были равны?
Решение
Отнесём к одной группе число an, а к другой – число an–1. Затем будем последовательно относить числа an–2, an–3, ..., a1 к той группе, в которой сумма чисел меньше (если суммы равные, то число можно относить к любой группе). Пусть Δk ≥ 0 – разность между суммами чисел в группах, полученных после отнесения к ним ak. Покажем, что Δk ≤ ak.
Действительно, Δn–1 = an – an–1 ≤ 2an–1 – an–1 = an–1. Ясно также, что если Δk ≤ ak, то Δk–1 = |Δk–1 – ak–1| и – ak–1 ≤ Δk – ak–1 ≤ 2ak–1 – ak–1 = ak–1.
После того как мы распределим по двум группам все числа, получим группы с суммами S1 и S2, причём |S1 – S2| ≤ a1 = 1. По условию число S1 + S2 чётно, поэтому S1 = S2.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь