Нахождение делителей 2010!

[Mixo123]

Здравствуйте, уважаемые Математики!
Намедни писал пробное ЕГЭ по математике за 10 класс (без логарифмов), где в С-уровне (сложные задания) встретил задачку, которую решить не смог.
Задача мне показалась интересной и я решил запомнить её, чтобы дома выяснить, как всё же она решается.

Собственно задача:
Найти наибольшее $n \in \mathbb{N}$, для которого каждое из чисел $k^k$ при $k=1,2,...,n$ является делителем числа $2010! = 1*2*3*...*2010$.

Собственные соображения:
Единственное, что напрашивается на ум - неравенство вроде $k^k \le 2010!$, но при этом понимаю, что это вряд ли правильное и наиболее оптимальное решение, а также то, что решить подобное неравенство "ручками" вряд ли возможно... Может тут прогрессии какие-нибудь есть или ещё что-то?

Как же это тогда решить?
Буду очень рад узнать, как бы так "красиво" и верно решить эту задачу.

[Xaositect]

Есть известная задачка.
Определить максимальное $k$, для которого $2^k$ является делителем $k!$
Определяется оно таким образом: количество чисел от 1 до $n$ (множителей в факториале), которые делятся на 2 + кол-во тех, что делятся на 4 + и т.д.
Получается сумма
$\sum_{i=0}^{\infty} \lfloor\frac{n}{2^i}\rfloor$
Она на самом деле конечная.
Еще надо заметить, что здесь используется то, что 2-простое число, а если бы там было, скажем, 10, то надо делить не на степени 10, а на степени 5 (на каждую пятерку своя двойка в произведении уж точно найдется)

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

[PAV]

Мне кажется, что ответ здесь 46 (т.е. $47^{47}$ уже не будет делителем), а отталкиваться надо от корня $\sqrt{2010}$. Ясно, что числа $n$, которые меньше этого корня, условию удовлетворяют.

[venco]

Ваше неравенство совершенно ни при чём.
Правильное неравенство содержит $n^2$.
Вам надо найти такое $m=n+1$, что $2010!$ не делится на $m^m$.
А теперь сопоставьте расложение на простые множители $2010!$ и $m^m$, и подумайте, при каких условиях делиться не будет.

[Mixo123]

Ух, как всё сложно... На это задание, по идее, должно уходить не более 15 минут, т.к. суммарное время на ЕГЭ, которое нам давали (только средний и сложный уровни), - 3 часа...
Xaositect, нам в 10 классе не рассказывали о суммах.
Но, следуя Вашей логике, у меня должна получится сумма вроде $\sum_{i=0}^{\infty} \frac{1005}{k^i}$?
Тогда эта сумма равна $\sum_{i=0}^{\infty}\frac{1005}{k^i} = \frac{1005 k}{k-1}$?

venco, в разложение $2010!$ точно входят все простые числа до 2003, причём некоторые из них, по идее, даже в какой-то довольно большой степени.
Также понятно, что $2010!$ однозначно делится на все числа от 1 до 2010 включительно и на любое из их произведений (скажем, $5*3*7$, т.к. все 3 числа так или иначе найдутся в этом факториале).
Это значит, что $k^k$ должно раскладываться только на числа, на которые делится $2010!$...
Но это, опять же, мало о чём мне говорит.

PAV, а откуда там кв.корень?

Но всё это должно решаться как-то совсем-совсем просто... Всё-таки 10 класс общеобразовательной школы с довольно слабым уровнем математики...

[venco]

Mixo123 в сообщении #215312 писал(а):

Но всё это должно решаться как-то совсем-совсем просто... Всё-таки 10 класс общеобразовательной школы с довольно слабым уровнем математики...

ЕГЭ, в идеале, должен дифференцировать учеников с разным уровнем знаний и умений. Соответственно, в нём должны присутствовать и задачи, которые по зубам только небольшой части продвинутых и сообразительных учеников.
Данная задача не требует особенных знаний чтобы убедиться, что $2010!$ не делится на $47^{47}$ и делится на все меньшие $k^k$.

[PAV]

Ну смотрите. Возьмем число $n$. Самое банальное, что приходит в голову, чтобы набрать $n$ раз по $n$ - это взять числа $n$, $2n$, $3n$,...,$n\cdot n=n^2$. Ясно, что произведение этих чисел будет делиться на $n^n$. Значит, если $n^2\le 2010$ (что равносильно $n\le\sqrt{2010}$), то такие числа $n$ нам подходят независимо от того, простые они или составные. Заметим, что $\sqrt{2010}$ лежит между 44 и 45.

Теперь подумайте, что можно сказать про ситуацию, когда $n$ - простое число и $n^2>2010$. Ну и дальше порассуждайте в том же духе.

[RIP]

Xaositect в сообщении #215289 писал(а):

Получается сумма
$\sum_{i=0}^{\infty} \lfloor\frac{n}{2^i}\rfloor$

Суммировать надо, начиная с $i=1$.

[Mixo123]

venco, ну коли разделение на сильных и слабых, то тогда всё нормально, а также ясно, отчего мне не дано решать такие вещи.
Просто почему-то раньше я считал, что ЕГЭ - это простейшие задания по математике для школьников с общим образованием, среди которых С-уровень - сложнейшие.

И ещё: получается, что ${46}^{46}$ - это скорее уж тогда минимальное n, при котором $k^k$ делит $2010!$. Не обратил я внимания на то, что делиться должны и все предыдущие $k^k$, искал какое-то небесное число (отсюда и неравенство взялось).

PAV, насколько я понял, 47 нам не походит потому, что не содержится 47 раз в самом числе. А 47 - это и есть простое число. Собственно говоря, ${47^2} > 2010$.
В свою очередь $n={45}$ нам подошло из-за того, что это, по сути, $5 * {3^2}$, то есть оно состоит из простых чисел 5 и 3 (ну или хотя бы 15 возьмём - ${15}^{15}$ тоже входит в $2010!$).

Значит, корень нам понадобился в основном для того, чтобы найти своего рода "отправную точку", и от неё идти (в сторону больших) к ближайшему простому числу, верно?

Т.к. всё, что будет составным и сможет разложиться на простые числа, меньшие 47, можно будет, как в случае с 48, разложить на что-то такое, что удовлетворяет нашим условиям - на $24*2$, например. В случае с 46 история такая же.

Теперь правильно мыслю?

p.s.: заранее спасибо, что именно объясняете, что да как, а не просто кидаете решение. Думаю, таким образом удастся в конце концов минимизировать количество задаваемых вам всем вопросов.

[PAV]

Собственно, главное, что нужно понять в связи с этой задачей - это научиться находить максимальную степень, с которой заданное простое число $p$ входит в факториал $N!$. Мои подсказки должны помочь решить эту задачу.

ну и да, квадрат помогает найти отправную точку, до которой все точно хорошо, а дальше мы последовательно добираемся до первого простого числа, на котором и останавливаемся.