2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу 1, 2  След.
 
 Задача C6 на нахождение делителя факториала
Сообщение18.01.2015, 13:51 
Здравствуйте. Задали на выходные решить первый вариант из книжки Л.Д. Лаппо и М.А. Попова ( ЕГЭ профильный уровень )

Попалась такая задачка:
Найдите наибольшее натуральное $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, но как дальше развить эту идею не знаю.

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

 
 
 
 Re: Задача C6 на нахождение делителя факториала
Сообщение18.01.2015, 13:53 
Аватара пользователя
sandr1x в сообщении #964130 писал(а):
Единственное ограничение, которое приходит на ум $2010! \leqslant n^{n^4}$
Отсюда извлечь оценку сверху (вряд ли она будет очень высокой), а там все перепробовать руками.

 
 
 
 Re: Задача C6 на нахождение делителя факториала
Сообщение18.01.2015, 13:54 
Аватара пользователя
Ну, может попробовать кроме 2 еще 3, 4 и т.п.? Подсчитать количество вхождений конкретного делителя гораздо проще.

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

 
 
 
 Re: Задача C6 на нахождение делителя факториала
Сообщение18.01.2015, 14:17 
Цитата:
$2010! = 1\cdot2\cdot3...2009\cdot2010$ делиться на $n^{n^4}$

Цитата:
$2010! \leqslant n^{n^4}$

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

 
 
 
 Re: Задача C6 на нахождение делителя факториала
Сообщение18.01.2015, 15:11 
Аватара пользователя
iifat в сообщении #964135 писал(а):
Не думаю, что вам за 50 придётся переходить.


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

 
 
 
 Re: Задача C6 на нахождение делителя факториала
Сообщение18.01.2015, 15:24 
g______d в сообщении #964180 писал(а):
По-моему, нолик лишний :)
Ну, все-таки не настолько. :D

 
 
 
 Re: Задача C6 на нахождение делителя факториала
Сообщение18.01.2015, 15:47 
Аватара пользователя
Если очень грубо, призвав Стирлинга, прологарифмировав и извлекнув (как правильно??? :oops: ) корень 4 степени, то получится около 10?

 
 
 
 Re: Задача C6 на нахождение делителя факториала
Сообщение18.01.2015, 16:00 
При 9 уже перебор будет. Но руками это трудно получить, проще границу подальше отодвинуть.

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

 
 
 
 Re: Задача C6 на нахождение делителя факториала
Сообщение18.01.2015, 16:18 
Аватара пользователя
nnosipov, почему трудно? Да устно! Логарифм возьмём десятиричный. Две тыщи делить на е будет примерно восемьсот. Логарифм около трёх. Получим примерно две тысячи умножить на три, то есть шесть тысяч. Корень — восемьдесят, ещё корень — девять. :-)

 
 
 
 Re: Задача C6 на нахождение делителя факториала
Сообщение18.01.2015, 16:59 
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), а так как дальше степень будет только расти, то и перебирать нет смысла.

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

 
 
 
 Re: Задача C6 на нахождение делителя факториала
Сообщение18.01.2015, 18:04 
gris, Стирлинг как бы не совсем школьный способ. Тут нужно что-то совсем сермяжное.

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

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

 
 
 
 Re: Задача C6 на нахождение делителя факториала
Сообщение30.10.2015, 16:47 
Детский сад. Задача почему-то показалась сложной, но пока искал ответ, решил её сам. Итак решение.
Берем 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.

 
 
 [ Сообщений: 17 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group