|
Доказать, что среди любых $%2^{n+1}-1$% целых чисел найдется $%2^n$% чисел, сумма которых делится на $%2^n$%. задан 11 Ноя '14 19:09 
aid78 |
|
Более сильное утверждение: среди любых $%2n−1$% целых чисел найдется $%n$% чисел, сумма которых делится на $%n$%. Задача № 45 http://kvant.ras.ru/1971/07/resheniya_zadachnika_kvanta_ma.htm http://kvant.ras.ru/1971/08/resheniya_zadachnika_kvanta_ma.htm . Ещё замечательная статья: http://kvant.ras.ru/pdf/2010/2010-02.pdf (страница № 45). отвечен 11 Ноя '14 21:38 
EdwardTurJ @EdwardTurJ: среди известных мне доказательств этого утверждения (теорема Эрдёша-Гинзбурга-Зива) есть особенно короткое и эффектное алгебраическое рассуждение, основанное на лемме Олсона о групповых кольцах. В принципе, его можно адаптировать, переведя на школьный язык. Сам результат относится к 1961 году, а статья Олсона -- это примерно 1968 год.
(11 Ноя '14 22:47)
falcao
|
Надо заметить, что в такой формулировке условие неверно. Скажем, при $%n=1$% получается одно число, и двух вообще не найдётся. При $%n=2$% будет три числа, и четырёх там нет. При $%n=3$% утверждение тоже неверною Я думаю, что условие должно было звучать иначе. Скорее всего, было $%2^{n+1}-1$% целых чисел, среди которых надо найти $%2^n$%, сумма которых делится на $%2^n$%. В такой формулировке задача мне попадалась, и это "облегчённый" случай общего факта для $%2N-1$% чисел и делимости на $%N$% суммы $%N$% из них. Для степеней двойки это легко доказывается по индукции.
@falcao Спасибо, наверное условие действительно "среди $%2^{n+1}-1$% чисел выбрать $%2^n$% таких, что их сумма делится на $%2^n$%". Думаю, что у меня получится по индукции доказать.
@aid78: да, конечно. Там просто три раза можно выбрать по $%2^{n-1}$% чисел, поделив суммы на $%2^{n-1}$%, а потом из трёх чисел взять два одной чётности.