Задача C6 на нахождение делителя факториала

[sandr1x]

Здравствуйте. Задали на выходные решить первый вариант из книжки Л.Д. Лаппо и М.А. Попова ( ЕГЭ профильный уровень )

Попалась такая задачка:
Найдите наибольшее натуральное $n$, при котором число $2010! = 1\cdot2\cdot3...2009\cdot2010$ делиться на $n^{n^4}$.

Ничего подобного еще в школе не решали.
Единственное ограничение, которое приходит на ум $2010! \leqslant n^{n^4}$ , но не думаю, что это можно решить.
Раскладывать ($2010! = 2009! \cdot 2010$; $2010! = 2008! \cdot 2009 \cdot 2010$ и т.д.) тоже особого смысла не вижу. Чтобы найти ответ придется записать все множители от 1 до 2010 и у каждого найти делители, а это очень долго; на ЕГЭ времени точно не хватит.
Есть предположение, что ответом будет степень двойки, т.к каждый второй множитель кратен 2, но как дальше развить эту идею не знаю.

Прошу вашей помощи.

[ИСН]

sandr1x в сообщении #964130 писал(а):

Единственное ограничение, которое приходит на ум $2010! \leqslant n^{n^4}$

Отсюда извлечь оценку сверху (вряд ли она будет очень высокой), а там все перепробовать руками.

[provincialka]

Ну, может попробовать кроме 2 еще 3, 4 и т.п.? Подсчитать количество вхождений конкретного делителя гораздо проще.

[iifat]

Теоремку о показателе простого числа в факториале знаете? Я бы просто начал подсчёт степеней простых чисел в факториале. $n^{n^4}$ растёт очень быстро. Не думаю, что вам за 50 придётся переходить. А потом подбором найти составное произведение.

[Kras]

Цитата:

$2010! = 1\cdot2\cdot3...2009\cdot2010$ делиться на $n^{n^4}$

Цитата:

$2010! \leqslant n^{n^4}$

что это?
число меньше делителя

[g______d]

iifat в сообщении #964135 писал(а):

Не думаю, что вам за 50 придётся переходить.

По-моему, нолик лишний :)

[Pphantom]

g______d в сообщении #964180 писал(а):

По-моему, нолик лишний :)

Ну, все-таки не настолько.

[gris]

Если очень грубо, призвав Стирлинга, прологарифмировав и извлекнув (как правильно??? ) корень 4 степени, то получится около 10?

[nnosipov]

При 9 уже перебор будет. Но руками это трудно получить, проще границу подальше отодвинуть.

[g______d]

Нет, ну хорошо, формально нужно проверять 5 и 6, потому что 6 могло оказаться лучше 5. Если уж быть совсем занудой, то еще 8. Но я не вижу, зачем какой-то больший перебор.

[gris]

nnosipov, почему трудно? Да устно! Логарифм возьмём десятиричный. Две тыщи делить на е будет примерно восемьсот. Логарифм около трёх. Получим примерно две тысячи умножить на три, то есть шесть тысяч. Корень — восемьдесят, ещё корень — девять.

[sandr1x]

Kras в сообщении #964146 писал(а):

Цитата:

$2010! = 1\cdot2\cdot3...2009\cdot2010$ делиться на $n^{n^4}$

Цитата:

$2010! \leqslant n^{n^4}$

что это?
число меньше делителя

Знак перепутал, торопился

-- 18.01.2015, 17:21 --

Вообщем всем большое спасибо.
Используя формулу $m=[\frac{N}{n}]+[\frac{N}{n^2}]+[\frac{N}{n^3}]...$ , а в данном случае $m=[\frac{2010}{2}]+[\frac{2010}{4}]...[\frac{2010}{1024}]$, получилось, что число $2010!$ делится на $2^{2002}$. Отсюда следует, что число $2010!$ делится на $4^{1001}$, т.е. $n^{n^4}=4^{4^4}=4^{256}$ подходит, т.е. проверять $n=2$ и $n=3$ проверять не надо. При проверке $n=5$ получается, что число $2010!$ делится на $5^{501}$, а $n^{n^4}=5^{5^4}=5^{625}$, т.е. перебор. Получается ответ: 4; что сходиться с ответами.

Всё верно?
Теперь не знаю, как объяснить, что дальше перебирать не имеет смысл

-- 18.01.2015, 17:38 --

Думаю имеет смысл продолжить перебор, пока степень не станет больше степени двойки (для $n^{n^4}$). Двойка встречается чаще всего(каждое второе число делится на 2), а так как дальше степень будет только расти, то и перебирать нет смысла.

[Евгений Машеров]

Выписываем четвёртые степени
1, 16, 81, 256, 625, 1296, 2401, 4096...
Смотрим, сколько раз в $n^{n^4}$ встречаются множители n, и найдётся ли их столько в 2010! (как посчитать - тут уже подсказали)...

[nnosipov]

gris, Стирлинг как бы не совсем школьный способ. Тут нужно что-то совсем сермяжное.

-- Вс янв 18, 2015 22:13:44 --

Если $n$ делится на простое $p \geqslant 5$, то в $n^{n^4}$ больше $p$-ек будет. Значит, в $n$ есть только двойки и тройки. Если троек хотя бы две, то привет, если двоек хотя бы три, то тоже. Значит, этого добра мало и надо только перебрать все случаи.

[yury_v]

Детский сад. Задача почему-то показалась сложной, но пока искал ответ, решил её сам. Итак решение.
Берем 2:$2^{16}$, т.е. нам нужно 16 двоек. 2010:2=1005 чисел делящихся на 2 - хватает
Берем 3:$3^{81}$, т.е. нам нужно 81 троек. 2010:3=670 чисел делящихся на 3 - хватает
Берем 4:$4^{256}$, т.е. нам нужно 256 четверок. 2010:4=502,5, т.е. 502 числа делящихся на 4 - хватает
Берем 5:$5^{625}$, т.е. нам нужно 625 пятерок. 2010:5=402 - мало

Но тут мы вспоминаем, что каждое мятое из этих 402 еще делится на 5 => 402:5=80,4, т.е. еще 80 пятерок 402+80=482 - мало.
Тогда вспоминаем что из этих 80 каждое пятое делится еще раз на 5 => 80:5=16, т.е. еще 16 пятерок 482+16=498 - мало.
Еще итерация 16:5=3,2 => еще 3 пятерки.
Итого, насобирали 498+3=501 пятерку, а нужно 625.
С 6 и т.д. будет еще хуже

Ответ 4.