Помогите решить задачу (принцип Дирихле и делимость чисел)

[bobadila]

Из сборника задач Н. В. Горбачева.
Доказать, что из совокупности любых $2^{n+1}-1$ целых чисел можно найти $2^n$ чисел, сумма которых делится на $2^n$.
В ответах указано, что доказать можно по индукции, но что-то уже для $n=2$ ничего не приходит в голову.

[RIP]

viewtopic.php?t=7670
topic10226.html

[Dave]

Если доказано для $n-1$, то нужно, воспользовавшись этим утверждением, последовательно выбрать 3 группы по $2^{n-1}$ чисел, в каждой из которых сумма делится на $2^{n-1}$, а потом выбрать из этих групп подходящую пару.