2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Какое наименьшее количество множителей требуется вычеркнуть?
Сообщение04.03.2016, 14:35 
Аватара пользователя


01/12/11

8634
Какое наименьшее количество множителей требуется вычеркнуть из числа 2016! так, чтобы произведение оставшихся множителей оканчивалось на 2016?

Иными словами, чему равен 2016-й член последовательности 0 0 1 0 2 2 5 2 5...?

 Профиль  
                  
 
 Re: Какое наименьшее количество множителей требуется вычеркнуть?
Сообщение06.03.2016, 10:53 
Заслуженный участник
Аватара пользователя


13/08/08
14496
В преддверии празднования торжествующего феминизьма некогда и подумать над интересной задачей. Не лезет, батька, ничего в голову. Даже сметана на помогает.
Ясно, что всегда можно вычеркнуть всю середину факториала. Ясно, что можно оставить сомножители $2016$. Но это же далеко не минимум. Необходимо к вычёркиванию всё, что делится на $10$.
Вот для предыдущего числа $2015$ хотя бы много, что придётся вычеркнуть. Во-первых, все чётные числа. Во вторых, все делящиеся на $5$ кроме одного.
Призываю любителей поделиться идеями!

 Профиль  
                  
 
 Re: Какое наименьшее количество множителей требуется вычеркнуть?
Сообщение06.03.2016, 11:06 
Аватара пользователя


29/04/13
8846
Богородский
gris в сообщении #1104523 писал(а):
Необходимо к вычёркиванию всё, что делится на $10$.

Вы хотели сказать, все $403$ сомножителя, которые делятся на $5$ ? :wink:

 Профиль  
                  
 
 Re: Какое наименьшее количество множителей требуется вычеркнуть?
Сообщение06.03.2016, 13:18 
Заслуженный участник
Аватара пользователя


13/08/08
14496
Я хотел сказать, что в этой задаче можно рассуждать. Например, у меня получились очень милые детские рассуждения для $10!$. Вот и стало интересно, существуют ли взрослые для очень больших чисел :?:
Можно попробовать подобраться к задаче сзади. То есть набрать максимальное число различных натуральных чисел не больших $N$, так чтобы их произведение кончалось на $N$. Тут идея разложить само число на множители, а также числа, которые не меняют конца произведения.
Потом можно спрятать повторяющиеся числа в попарных произведениях. Например:

$2016=1\cdot 2\cdot 2\cdot 2\cdot 2\cdot 2\cdot 3\cdot 3\cdot 7$

$10001=73\cdot 137$

$20001=3\cdot 59\cdot 113$

$30001=19\cdot 1579$

И это даёт $1\cdot 2\cdot 4\cdot 6\cdot 7\cdot 9\cdot 38\cdot 59\cdot 73\cdot 113\cdot 137\cdot 1579=12098217720962016$

Конечно, тут тоже наличествует тупой перебор. Да и докуда перебирать, если вот $56321230001=31\cdot 53\cdot 89\cdot 283\cdot 1361$ :shock:

Вместе с тем, количество чётных сомножителей может быть большим. Например, $22016=2^9\cdot 43$. Чего-то мне кажется, что я в упор не вижу простого решения :-(

 Профиль  
                  
 
 Re: Какое наименьшее количество множителей требуется вычеркнуть?
Сообщение07.03.2016, 01:56 


08/09/13
210
Компьютерное решение (динамическим программированием) показало, что достаточно вычеркнуть все кратные $5$ и ещё одно число $1449$.

 Профиль  
                  
 
 Re: Какое наименьшее количество множителей требуется вычеркнуть?
Сообщение07.03.2016, 08:58 
Аватара пользователя


29/04/13
8846
Богородский
Иными словами, результат выражения

$$\frac{2016!}{5^{403}\cdot403!\cdot1449}$$

заканчивается на $2016$ ?

-- 07.03.2016, 09:02 --

Это $4627$-значное число, но вот концовку мне Alpha не показывает...

 Профиль  
                  
 
 Re: Какое наименьшее количество множителей требуется вычеркнуть?
Сообщение07.03.2016, 09:32 
Заслуженный участник
Аватара пользователя


13/08/08
14496
Можно все умножения делать по модулю $10000$. Собственно, я так и считал прямо в эксельке, уповая, что не придётся залезать в мудрёную динамику fractalon. Как подсказал Yadryara, подготовил столбец из $2016-403$ чисел, перемножил их все, оставляя только 4 последние цифры. Кончается на $1184$. Приготовился постепенно удалять из столбца числа по одному, потом по два... Хотел даже анализировать вначале только последнюю цифру, но перебор неожиданно закончился на первом же проходе.
Итак, $K_{2016}=1612$.
Жалко, что не получилось теоретически :-)
.

 Профиль  
                  
 
 Re: Какое наименьшее количество множителей требуется вычеркнуть?
Сообщение07.03.2016, 20:11 


08/09/13
210
Математическое решение, видимо, должно было заключаться в том, чтобы мы перемножили все множители кроме кратных пяти по модулю $10000$, а потом по этому же модулю разделили результат на 2016. И тут магическим образом оказалось бы, что это одно из оставшихся чисел.

(Оффтоп)

И ничуть там не мудрёная динамика: $d_{n,k}$ - минимальное количество множителей, которое нужно вычеркнуть из $n!$ чтобы последними четырьмя цифрами было число $k$. Решает за $O(nk)$, порядка $10^7$ операций. Хорошая машина за секунду управится (моя, правда, не управилась).

 Профиль  
                  
 
 Re: Какое наименьшее количество множителей требуется вычеркнуть?
Сообщение07.03.2016, 20:48 
Заслуженный участник
Аватара пользователя


13/08/08
14496
А как можно разделить $1184$ на $2016$ по модулю $10000$?
Я только перебором могу :oops:
Я под математическим решением понимал не требующее компьютера под рукой. То есть эта задача вполне годится для школьников-программеров, а вот если в лесу? При каком $N$ эта задача интересна и не обременительна для решения на листочке бумаги? Я думаю, что какие-то формулы существуют для умножения по модулю прогрессий. Впрочем, для решения подобных задач всегда есть искушение перед подумать начирикать примитивный скрипт. А уж если серьёзный пакет имеется... :-)

 Профиль  
                  
 
 Re: Какое наименьшее количество множителей требуется вычеркнуть?
Сообщение07.03.2016, 23:17 
Заслуженный участник


04/05/09
4596
Исключить надо как минимум 404 множителя - 403 кратных 5, и одно из $199+625k$.

 Профиль  
                  
 
 Re: Какое наименьшее количество множителей требуется вычеркнуть?
Сообщение07.03.2016, 23:24 
Аватара пользователя


11/06/12
10390
стихия.вздох.мюсли
Yadryara в сообщении #1104787 писал(а):
Это $4627$-значное число, но вот концовку мне Alpha не показывает...
Не беспокойтесь. Mathematica мне показала. Заканчивается. Если хотите, могу переслать число полностью вам в ЛС ;-D

 Профиль  
                  
 
 Re: Какое наименьшее количество множителей требуется вычеркнуть?
Сообщение08.03.2016, 00:09 
Заслуженный участник
Аватара пользователя


09/09/14
6328
Yadryara в сообщении #1104787 писал(а):
Это $4627$-значное число, но вот концовку мне Alpha не показывает...
Не то чтобы в лесу, но за 2 минуты я заставил Альфу показать все цифры этого числа. Чтобы обхитрить, я задал вопрос чуточку сложнее (добавил ещё 5 в знаменатель):$$\frac{2016!}{5^{404}\cdot403!\cdot1449}$$

 Профиль  
                  
 
 Re: Какое наименьшее количество множителей требуется вычеркнуть?
Сообщение08.03.2016, 02:14 
Аватара пользователя


01/12/11

8634
gris
Yadryara
fractalon
venco
Aritaborian
grizzly
Спасибо!

 Профиль  
                  
 
 Re: Какое наименьшее количество множителей требуется вычеркнуть?
Сообщение08.03.2016, 06:12 
Аватара пользователя


29/04/13
8846
Богородский
venco в сообщении #1104950 писал(а):
Исключить надо как минимум 404 множителя - 403 кратных 5, и одно из $199+625k$.

А вот и ответ в общем виде. Ежели не хочется вычёркивать $1449$, к вашим услугам $199$ или $824$.

Почему множитель $625$ ?

Не забывая, что любое целое число, оканчивающееся на $2016$, делится на $16$, получим:

$10000k+2016 = 16(625k+126)$.

Вопрос ещё и в том, можно ли более-менее кратко объяснить, откуда берётся $199$...


grizzly в сообщении #1104963 писал(а):
Не то чтобы в лесу, но за 2 минуты я заставил Альфу показать все цифры этого числа. Чтобы обхитрить, я задал вопрос чуточку сложнее (добавил ещё 5 в знаменатель):$$
\frac{2016!}{5^{404}\cdot403!\cdot1449}$$

Очень ловко! Как догадались?

Действительно, стоит только сделать результат не целым, а рациональным, как "Альфа" начинает показывать даже столь длинные числа целиком. Причём показывает сразу же, даже без нажатия кнопки "More digits"!

-- 08.03.2016, 06:23 --

Если желаешь увидеть чему точно равно огромное число $2016!$, превращаешь его в рациональное, разделив на большее простое. Например на $2111$. Вуаля! Ответ готов!

 Профиль  
                  
 
 Re: Какое наименьшее количество множителей требуется вычеркнуть?
Сообщение08.03.2016, 14:26 


08/09/13
210
gris в сообщении #1104905 писал(а):
А как можно разделить $1184$ на $2016$ по модулю $10000$?

Для этого надо разделить $74$ на $126$ по модулю $625$ (просто поделил все числа на $16$, чтобы модуль и делитель стали взаимопростыми).
Это делается просто, можно и на бумажке, с помощью обратного элемента по модулю. А это через алгоритм Евклида: http://e-maxx.ru/algo/reverse_element

Отсюда и $625$ и $119$.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 22 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: epros


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group