Докажите, что из любых 2^(n+1) натуральных чисел можно выбрать ровно 2^n, сумма которых делится на 2^n.

Дано

Имеется набор из $2^{n+1}$ натуральных чисел.

Найти

Доказать, что из этого набора можно выбрать ровно $2^n$ чисел, сумма которых делится на $2^n$.

Решение

Рассмотрим задачу для произвольного $n$. Доказательство проведем методом индукции.

База индукции: Пусть $n = 1$. У нас есть $2^{1+1} = 4$ натуральных числа. Нужно выбрать $2^1 = 2$ числа, сумма которых делится на $2^1 = 2$. Среди любых 4 чисел по принципу Дирихле найдутся как минимум два числа одной четности (так как остатков при делении на 2 всего два: 0 и 1). Сумма двух чисел одной четности всегда четна (делит...