Задача 78129

Темы:    [ Теория алгоритмов (прочее) ] [ Четность и нечетность ]

Сложность: 4 Классы: 9,10,11

Условие

Дано n целых чисел  a₁ = 1,  a₂, a₃, ..., a_n, причём   a_i ≤ a_i+1 ≤ 2a_i  (i = 1, 2,..., n – 1)  и сумма всех чисел чётна. Можно ли эти числа разбить на две группы так, чтобы суммы чисел в этих группах были равны?

Решение

  Отнесём к одной группе число a_n, а к другой – число a_n–1. Затем будем последовательно относить числа a_n–2, a_n–3, ..., a₁ к той группе, в которой сумма чисел меньше (если суммы равные, то число можно относить к любой группе). Пусть  Δ_k ≥ 0  – разность между суммами чисел в группах, полученных после отнесения к ним a_k. Покажем, что  Δ_k ≤ a_k.
  Действительно,  Δ_n–1 = a_n – a_n–1 ≤ 2a_n–1 – a_n–1 = a_n–1.  Ясно также, что если  Δ_k ≤ a_k,  то  Δ_k–1 = |Δ_k–1 – a_k–1|  и  – a_k–1 ≤ Δ_k – a_k–1 ≤ 2a_k–1 – a_k–1 = a_k–1.
  После того как мы распределим по двум группам все числа, получим группы с суммами S₁ и S₂, причём  |S₁ – S₂| ≤ a₁ = 1.  По условию число  S₁ + S₂  чётно, поэтому  S₁ = S₂.

Источники и прецеденты использования

олимпиада
Название	Московская математическая олимпиада
год
Номер	20
Год	1957
вариант
Класс	10
Тур	2
задача
Номер	5