2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

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

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Задача C6 на нахождение делителя факториала
Сообщение18.01.2015, 13:51 


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

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


18/05/06
13435
с Территории
sandr1x в сообщении #964130 писал(а):
Единственное ограничение, которое приходит на ум $2010! \leqslant n^{n^4}$
Отсюда извлечь оценку сверху (вряд ли она будет очень высокой), а там все перепробовать руками.

 Профиль  
                  
 
 Re: Задача C6 на нахождение делителя факториала
Сообщение18.01.2015, 13:54 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Задача C6 на нахождение делителя факториала
Сообщение18.01.2015, 13:58 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Задача C6 на нахождение делителя факториала
Сообщение18.01.2015, 14:17 


10/12/14

345
http://lj.rossia.org /users/tiphareth/
Цитата:
$2010! = 1\cdot2\cdot3...2009\cdot2010$ делиться на $n^{n^4}$

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

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

 Профиль  
                  
 
 Re: Задача C6 на нахождение делителя факториала
Сообщение18.01.2015, 15:11 
Заслуженный участник
Аватара пользователя


08/11/11
5940
iifat в сообщении #964135 писал(а):
Не думаю, что вам за 50 придётся переходить.


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

 Профиль  
                  
 
 Re: Задача C6 на нахождение делителя факториала
Сообщение18.01.2015, 15:24 
Заслуженный участник


09/05/12
25179
g______d в сообщении #964180 писал(а):
По-моему, нолик лишний :)
Ну, все-таки не настолько. :D

 Профиль  
                  
 
 Re: Задача C6 на нахождение делителя факториала
Сообщение18.01.2015, 15:47 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Задача C6 на нахождение делителя факториала
Сообщение18.01.2015, 16:00 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Задача C6 на нахождение делителя факториала
Сообщение18.01.2015, 16:14 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Задача C6 на нахождение делителя факториала
Сообщение18.01.2015, 16:18 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Задача C6 на нахождение делителя факториала
Сообщение18.01.2015, 16:59 


18/01/15
2
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 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Задача C6 на нахождение делителя факториала
Сообщение18.01.2015, 18:04 
Заслуженный участник


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

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

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

 Профиль  
                  
 
 Re: Задача C6 на нахождение делителя факториала
Сообщение30.10.2015, 16:47 


30/10/15
1
Детский сад. Задача почему-то показалась сложной, но пока искал ответ, решил её сам. Итак решение.
Берем 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