Найдите такое наибольшее целое $%k$%, что хотя бы для одного натурального $%n>1000$% число $%n!=1⋅2⋅...⋅n$% делится на $%2^{n+k+2}$%.

задан 22 Ноя '14 15:40

изменен 22 Ноя '14 18:03

%D0%92%D0%B8%D1%82%D0%B0%D0%BB%D0%B8%D0%BD%D0%B0's gravatar image


9917

10|600 символов нужно символов осталось
3

Для выяснения того, на какую максимальную степень двойки делится $%n!$%, имеется такая формула: $$\left\lfloor\frac{n}{2}\right\rfloor+\left\lfloor\frac{n}{4}\right\rfloor+\left\lfloor\frac{n}{8}\right\rfloor+\cdots.$$ Например, $%100!$% делится на $%2^m$%, где $%m=50+25+12+6+3+1=97$%, но не делится на $%2^{m+1}$%.

Обоснование довольно простое: среди чисел от $%1$% до $%n$% есть ровно $%\lfloor\frac{n}2\rfloor$% чётных, и от каждого из них в произведение поступает множитель 2. Те из них, которые делятся на 4, а их имеется $%\lfloor\frac{n}4\rfloor$%, вносят ещё один дополнительный множитель, и так далее.

Заметим, что сумма чисел из формулы не превосходит $%\frac{n}2+\frac{n}4+\cdots+\frac{n}{2^s}=n(\frac12+\frac14+\cdots+\frac1{2^s})$%, что строго меньше $%n$%. Через $%s$% здесь обозначено наибольшее число, для которого $%2^s\le n$%. Вывод: $%n!$% никогда не делится на $%2^n$%.

Если $%n$% является степенью двойки, $%n=2^s$%, то сумма из формулы равна $%2^{s-1}+2^{s-2}+\cdots+2+1=2^s-1=n-1$%, поэтому $%n!$% может делиться на $%2^{n-1}$%. Из сказанного следует, что $%k=-3$%, так как существуют степени двойки, большие 1000 (в частности, $%1024!$% делится на $%2^{1023}$%). При этом значение $%k$% увеличить до $%-2$% уже нельзя.

ссылка

отвечен 22 Ноя '14 16:38

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×3,686
×186

задан
22 Ноя '14 15:40

показан
1819 раз

обновлен
22 Ноя '14 16:38

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru