Задачка на метод мат.индукции

[Angelina]

Кто знает как доказать, что среди любых $2^{n+1}$ натуральных чисел можно выбрать ровно $2^n$ чисел, сумма которых делится на $2^n$.
Понимаю, что надо рассмотреть остатки от деления чисел на $2^n$ и строить доказательство по индукции, но уж очень оно громоздкое выходит!
Помогите пожалуйста!


включил BBCode и смайлики // нг

[Dandan]

Можно сразу показать, что из $(2^{n+1}-1)$-го числа всегда можно выбрать $2^n$, сумма которых делится на $2^n$.
По индукции из $(2^n-1)$-го числа можно выбрать $2^{n-1}$, сумма которых делится на $2^{n-1}$. Ну так выберем из наших $2^{n+1}-1$ такие $2^{n-1}$ чисел. Дальше, среди остальных чисел опять можем выбрать аналогичный набор. Короче, среди $2^{n+1}-1$ мы можем выбрать три набора по $2^{n-1}$ таких, что сумма чисел в каждом наборе делится на $2^{n-1}$. Остается правильно эти наборы скомпоновать


Можно доказать обобщение этого утверждения - из (2n-1)-го числа всегда можно выбрать n, сумма которых делится на n, но это намного сложнее.

[Angelina]

Ок.
Спасибо за совет, я разобралась.

[neo66]

Dandan писал(а):

Можно доказать обобщение этого утверждения - из (2n-1)-го числа всегда можно выбрать n, сумма которых делится на n, но это намного сложнее.

А какая идея доказательства для простых n?

[Dandan]

а не знаю, у меня самому для простых не получилось доказать, но мне говорили, что когда-то в кванте про это статья была или чето типа такого.

[RIP]

А именно: "Квант" 1971, № 8, решение задачи М45 (очень красивое решение).

[neo66]

Спасибо! Задача красивая, а изобретать велосипед лень.