#141

Олимпиадная задача по теории чисел! Делимость, натуральные числа, основная теорема арифметики, целая часть числа и многое другое!
ЗАДАЧНИК КО ВСЕМ РОЛИКАМ: topic-135395111_35874038
МОИ КУРСЫ: market-135395111
УСКОРИТЬ ПРОЦЕСС СОЗДАНИЯ НОВОГО ВИДЕО: www.donationalerts.ru/r/wildma...
VK: wildmathing
Здесь разбирается красивая задача по теории чисел, которая была на олимпиаде «Физтех» в 2011 году. Затрагиваются вопросы делимости, основная теорема арифметики, факториал числа, простые числа, свойства степеней и не только. В общем, вся школьная арифметика работает на руку! Если вам интересна математика, обязательно подпишитесь на канал: здесь есть, что посмотреть!
ВАЛЕРИЙ ВОЛКОВ: • Video
0:00 - Вступление
0:20 - Юбилей Валерия Волкова
0:55 - Рассмотрение частных случаев
1:27 - Обобщение
2:00 - Интересный случай!
3:20 - Контрпример
4:32 - Ответ
ДРУГИЕ ХОРОШИЕ ЗАДАЧИ ПО ТЕОРИИ ЧИСЕЛ
#76. • #76. ТЕОРИЯ ЧИСЕЛ! Зад...
#77. • #77. КАК РЕШАТЬ ЗАДАЧИ...
#84. • #84. КРУТАЯ ЗАДАЧА про...

[@Knantro]

84 почему нет?

[@WildMathing]

По условию задачи мы ищем наибольшее натуральное n, для которого 6500! делится на КАЖДОЕ из чисел k^k. И если для 83 делимости нет, то работать с большими числами не нужно.

[@Knantro]

Тьфу, точно! Спасибо)

[@WildMathing]

Пожалуйста!

[@Adam-ug1iv]

я тоже сначало подумал, что автор ошибся, но спомнил условие и все прошло

[@eyvgenigusseltcev3413]

Я тоже думал, где 84 потом еще раз посмотрел условие

[@jackjones8790]

Это просто лучший канал, математическое сокровище, почему же у вас так мало подписчиков

[@WildMathing]

Спасибо за добрые слова! В подписчиках главное качество, а не количество!

[@igorgrischenko6518]

Ну я хотябы понял, почему на 27 выскочил певец. Они умирают в 27. Как и моё чсв после просмотра этого видео.

[@WildMathing]

Ну, про музыкантов - верно, так что уже неплохо!

[@rhxahob2763]

Блин, а я-то все голову ломал, причем тут Кобейн. Чересчур тонкая для меня отсылка, мое уважение

[@user-bi5gx3oy4y]

Возможно, ты рофлишь, но это не Кобейн, это Моррисон

[@user-bi5gx3oy4y]

@@rhxahob2763, а извиняюсь, не досмотрел до момента с Куртом

[@user-vq2zf7jz2y]

Действительно, сочная задача! Чем больше встречаю подобное, тем яснее осознаю, что 19 номер ЕГЭ не такой уж и сложный. Спасибо!

[@WildMathing]

Рад, что задача придает оптимизма!

[@mafirka]

Валерия Волкова тоже обожаю♡ Равно как и Вас) Все каникулы вашим видео уделила и не пожалела ни секунды! Безумно интересно♡♡♡

[@WildMathing]

Большое спасибо за добрые слова!

[@user-lj2ll4qi9n]

[6500:3] + [2166:3] + [722:3] + [240:3] + [80:3] + [26:3] + [8:3] = 3244. Никаких программ не знаю. От формулы Лежандра, о которой писал один из комментаров, поплохело😕. Спасибо за видео)

[@ok-we5md]

это она и есть

[@elnurbda]

большое спасибо за видеоролик!

[@AlexeyEvpalov]

Можно проверять делимость, где k простое число. Спасибо за понятное решение.

[@dimss4213]

3:03 Очевидно, что искомая величина - это sum_i_1_to_inf(6500 // (3^i)). Т.к. функция 6500 // (3^x) не возрастает, то можно посчитать сумму до k = 7. Дальше будем прибавлять 0. Это равно 3244 P.S. Я не брутальный математик

[@user-bd4jn6cy1k]

Ты программист? Если да то на каком языке программируешь? Я на python уже 3 года.

[@dimss4213]

На тот момент, когда я написал тот комментарий, я программировал на python пару месяцев

[@ruslan_yefimov]

Написал за 15 минут код и нашёл ответ)))

[@user-nx1hl9yo2m]

Шутка с Джимом Моррисоном и Куртом Кобейном очень смешная!

[@WildMathing]

И смех и грех!

[@JayIsStudio]

А я ждал ещё кого-нибудь. Хендрикса хотя бы.

[@JayIsStudio]

А я раньше глупый был. Глупее, чем сейчас

[@JayIsStudio]

Возможно вернусь ещё через пару лет, если рекомендации напомнят

[@user-ys7se6ox4d]

Простое ну проще некуда) возьму на вооружение.

[@WildMathing]

C таким лексиконом ни один математический спор будет не страшен!

[@photon6156]

3244 троек заставил питон посчитать факториал, а затем делить на 3, пока делится. Выполняется меньше секунды, так что сегодня я думать не буду

[@sinusss]

Так неинтересно :(

[@ANUARKA]

интресно то, что 4 - 3247, то есть больше

[@user-mt7sn4ob4w]

К теме степени 3-ки - из любых трёх целых чисел идущих подряд ровно одно делится на 3 , Значит пробегая через 3 числа подряд соберём +1 к степени . Тогда степень 3 в разложении 6500 не меньше чем целая часть 6500/3~2166 , хватит за глаза

[@rhuslc]

А что если рассмотреть задачу для числа q! и проверить до какого числа k^k, где k = 1, 2, 3, 4,..., n, выполняется делимость q! на k^k? Тогда нужно разбить все числа на простые множители и число k тоже нужно разбить на простые множители, а затем среди них найти наибольшее число. Только вот ещё вопрос: а существует ли закономерность в разложении чисел на простые множители?

[@user-xb1mb9rq7f]

Сделаю вид, что понял. А так ооочень крутой канал!

[@WildMathing]

За комментарий - спасибо! Это видео не всем подходит, но на канале есть и попроще, и понятней. Да и вопросы всегда можно задать в комментариях.

[@firex2283]

3:10 sum(n=1, inf)[6500/3^n]

[@kyzinatra6391]

На счет троек. Теорема Лежандра это конечно хорошооо, но если проще, то можно сказать, что 1 число, которое делится на 3 встречается ну никак не реже, чем каждое третье. То есть троек в нашем числе не меньше чем 6500/3 ≈ 2166. ( это мы же еще квадраты не считали). Так что м головой хватит

[@user-zc9ni2fp7n]

Неужели я удостоился полностью понять задачу и решение

[@user-zc9ni2fp7n]

Хотел бы спросить у вас, по вашему мнению решение является понятным для 8-классника?

[@kuchma19]

Получил что-то много троек. Целых 3244. По формуле Лежандра действовал.

[@WildMathing]

Верно!

[@seriych]

Помню в свое время на заочной олимпиаде Физтеха тоже задачка понравилась. Там итоговый вопрос задачи был "найти все интересные числа" :-) Upd. Во, нашел: "Назовем натуральное число n интересным, если для него можно выбрать натуральное число M такое, что сумма цифр числа M равна n, и само число M делится на n. Найдите все интересные числа."

[@IvanIvanov-fd1ds]

А как найти их все?число M-число харшад.Их бесконечное множество

[@IvanIvanov-fd1ds]

Утверждение 1. Для любого натурального n существует число М с суммой цифр n. Доказательство. Рассмотрим числа 1, 10, 100, ...,10^k, ... Согласно принципу Дирихле, существует такой остаток r, что сколь угодно большое количество из этих чисел дают при делении на n остаток r. Теперь достаточно взять сумму n соответствующих чисел 10^k для разных таких k (можно и для совпадающих, но в количестве не более 9).

[@user-kk7bx3by2e]

респект за Кака)

[@na-kun2136]

А я заметил. Что вы превьюю поменяли.

[@ok-we5md]

ну мне лень считать но для этого есть формула лежандра

[@godj6075]

Тривиальная задачка. Оценка для троек n>3*1084*2167

[@ivansakovich7653]

Мне понравилось

[@van3961]

Спасибо за интересную задачку! Довольно быстро приходит мысль, что надо найти минимальное простое число, которое не встретится в 6500! нужное количество раз. 6500/79=82 -ещё подходит; 6500/83 =79 -недобор . Что 82 подходит - показать не сложно. Вот только что делать, если таблицы простых чисел под рукой нет?? Существует ли приемлемый способ, в полевых условиях, оценить - является ли число простым?

[@WildMathing]

Всегда пожалуйста! На самом деле, чтобы оценить, является ли число 83 простым, достаточно проверить лишь 8 делителей, это делается устно секунды за 2-3. Даже проверка того, является ли число 1031 простым, подразумевает лишь проверку лишь 30 делителей. Делается это так: рассматриваем делители от 2 до 31. Поскольку 32²=1024, этого вполне достаточно. 1031 нечетное => на 2,4, 6, ..., 30 не делится. По признаку делимости на 3, 5, 11, оно также не делится на 3, 5, 9, 11, 15, 21, 25, 27. Остается перебрать 7, 13, 17, 19, 23, 29, 31, что делается достаточно легко. То есть такой стандартный подход в виде перебора делителей займет не более минуты даже для нашего четырехзначного числа.

[@user-tp1xs6dk1h]

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

[@Uni-Coder]

Минут 40 думал. Понял, что в факторизации m! простое p будет в степени, не превышающей ОкрВниз(m/(p-1)), и не меньшей ОкрВниз(m/p), поэтому нам подходит число, точно меньшее 83. В то же время предыдущее число 82 = 41*2, 6500! делится на 2^6494, 6500! делится на 41^158, т.е. 6500! делится на 82^158, уже подходит. Видео не глядел

[@Uni-Coder]

Возьмем простое число p и найдем, в какой степени будет p в разложении m! на простые множители. Обозначим эту степень через S. Каждый p-й сомножитель в факториале делится на p, таким образом, получаем ОкрВниз(m/p) сомножителей, делящихся на p. То есть, уже получаем S >= ОкрВниз(m/p). Но среди них каждый p-й сомножитель делится на p ЕЩЕ РАЗ, т.е. получаем ОкрВниз(m/p) + ОкрВниз(ОкрВниз(m/p)/p). Среди тех, каждый p-й делится на p еще раз, получаем ОкрВниз(m/p) + ОкрВниз(ОкрВниз(m/p)/p) + ОкрВниз(ОкрВниз(ОкрВниз(m/p)/p)/p), и так далее. Заметим, что данная сумма не превышает геометрической прогрессии m/p + m/p^2 + m/p^3 + ... сумма которой равна m/(p-1). Получили m/p

[@gamemasters2189]

Пипец, я учусь в 8-м классе, учусь хорошо, на физ-мате, профильные предметы люблю, и щас физик выбрал 7 человек из класса (я в их числе) на доп занятия, там мы смотрим видеоуроки фоксфорда, он нам объясняет, если че не понятно, решаем задачи физтеха 9 класса, вроде все получается, но чем чаще я смотрю твои ролики, тем больше осознаю, что в старших классах мне хана, как такое понимать вообще можно???

[@WildMathing]

Уверен, в старших классах твой уровень будет так же хорош! Просто вводятся новые понятия, доказываются новые свойства, но это не значит, что задачи становятся принципиально глубже, чем олимпиадные номера 8-9 классов.

[@100MrTrolface100]

Вы можете посоветовать хорошую литературу по теории чисел?

[@WildMathing]

Да, конечно: kzbin.info/www/bejne/nZm7eneAi8aGY9U Кроме этого, всячески рекомендую книжку «Азы теории чисел» (Кноп К. А.)

[@100MrTrolface100]

@@WildMathing Спасибо большое!

[@WildMathing]

@@100MrTrolface100, ur welcome!

[@BudinCars]

ничего не понятно,но очень интересно!

[@user-wv8pl7ps7g]

Похожую задачу в 8 классе в физмате решали

[@user-ps1mh3hc8u]

Мы в садике еще такое решали

[@user-tp1xs6dk1h]

Очевидная даже для меня задача, переходящего в 7 класс. Мое решение заняло у меня секунд 30.

[@WildMathing]

Охотно верю!

[@user-jn2iz3qq1y]

Почему не было проверки для случая n=84, ведь то, что число n=83(простое) не удовлетворяет условию, то отсюда не следует, что число его превосходящее n=84 (составное) не является ответом, разве не нужно было доказать, что наибольшим составным удовлетворяющим ответу является 82, а простым 79?

[@WildMathing]

Смотри, вот проверим мы n=84, оно годится, но какой вывод? Это ведь не влияет на ответ: поскольку n=83 не годится, то нельзя сказать, что для всех n⩽84 делимость выполнена. А отдельные ответы для простых и составных чисел не просят вовсе, как-никак было четкое условие задачи (0:05).

[@user-jn2iz3qq1y]

Wild Mathing , да что-то я не заметил, думал нужно найти MAX

[@WildMathing]

Бывает!

[@valeriikovalevskyi21]

Как, сидя на олимпиаде и имея только (насколько мне известно) около 4 часов на 5 задач, можно дойти до числа 80? Озарение?

[@WildMathing]

Здесь совсем не нужен полный перебор. Главное - понять условие, затем найти наибольшее натуральное решение неравенства 6500>k², и сразу получатся те самые 80.

[@xxxmorkovka]

Попробуйте посмотреть 2х. Только хардкор

[@user-bh3bh1jh5y]

Пожалуйста помогите мне понять вопрос "Приведите пример натурального числа, произведение всех делителей которого оканчиваются на 6 нулей

[@WildMathing]

У каждого натурального числа есть свой уникальный набор делителей: скажем, 10 делится только на 1, 2, 5, и 10. Произведение всех делителей числа 10 равно 1*2*5*10=100. Тебя же просят привести пример такого числа, произведение всех делителей которого будет заканчиваться шестью нулями. Если не разберешься - дай знать!

[@user-bh3bh1jh5y]

Wild Mathing а такое может быть что оканчивается на 333 нуля

[@user-bh3bh1jh5y]

Wild Mathing я ещё не понимаю как найти такое число если на его расчеты уйдет тучу времени

[@WildMathing]

Произведение делителей-то? Может, конечно: например, 10^100 (он же гугол) делится на 10^100, 10^99, 10^98, 10^97... То есть в произведение его делителей на конце уж 333 нуля будет точно.

[@user-bh3bh1jh5y]

Wild Mathing огромное спасибо, чтобы я без вас делал.

[@user-jp1fo7gc7i]

Спасибо за видео, и вправду сочно вышло! Но вот что немного не понял: 80 мы ведь просто угадали, не так ли?

[@WildMathing]

Всегда пожалуйста! Нет-нет, угадывать здесь не приходится: 80 получено в результате решения неравенства 6500≥k², которое отражает желание разбить произведение 1∙2∙3∙...∙6500 на наибольшее количество k групп так, чтобы в каждой группе оказалось число кратное k.

[@user-jp1fo7gc7i]

@@WildMathing спасибо! Теперь все понятно! :)

[@WildMathing]

Не за что!

[@user-vr9uo3vb1w]

@@WildMathing тут кстати в общем случае несложно вывести лемму , что первым числом , которое будет прерывать этот ряд будет простое число. Потом понять , что оно приблизительно равно корню из 6500. И уже след шагом понять , что это 83. И все

[@WildMathing]

​@@user-vr9uo3vb1w, увы, такая лемма неверна. Число 9! делится на 1¹, 2², 3³, а вот на 4⁴ уже нет. k=4 - составное число, которое первое прерывает ряд.

[@user-mb5ld7ue2p]

степень вхождения простого р в n! : s= [n/p]+[n/p^2]+[n/p^3]+[n/p^4]+…

[@na-kun2136]

Вопрос. Как это можно было увидеть и как до этого можно было додуматься?

[@WildMathing]

Этому посвящена вся вторая минута ролика: специально на ощупь беру числа - исследую, что будет при таком значении, что при другом. К решению это не относится, зато на вопрос о том, как додуматься, отвечает.

[@persivald2148]

А по методу мат индукции доказать и найти можно?

[@WildMathing]

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

[@user-mm8hc5uu1e]

Что за звук на моменте 1:13 и 2:35?

[@WildMathing]

В лихие 90-ые, пожалуй, самой популярной игрой для 16-битных приставок был Mortal Kombat 3: Ultimate. При комбо-ударах иногда появлялась вставочка со звуком «trusy». Не знаю, зачем нужна такая здесь, но она точно нужна.

[@user-mm8hc5uu1e]

Wild Mathing если бы не она, аудитория была бы на порядок меньше 😄

[@user-mm8hc5uu1e]

Wild Mathing спасибо большое)

[@WildMathing]

Всегда пожалуйста!

[@ShevelevPhysMath]

@@WildMathing toasty) задача действительно сочненькая, прямо как тосты, двойная отсылочка выходит)

[@user-bd4jn6cy1k]

11¹¹ вроде не делится на 6500!. Или делится можете подсказать?

[@WildMathing]

Ни одна степень числа 11 не делится на 6500!, поскольку нечетное число не может делиться на четное

[@user-bd4jn6cy1k]

@@WildMathing Спасибо!

[@user-bd4jn6cy1k]

@@WildMathing ну тогда 10^10 это максимальное k. Или я что то не понял?

[@WildMathing]

@@user-bd4jn6cy1k, в исходной задаче мы все-таки исследуем, делится ли 6500! на k^k, а не наоборот. Делится ли 6500! на 11^(11)? Да, конечно, ведь 6500! по определению содержит множители 11, 22, 33, ..., 99, 110, 121. Так что в разложении на простые сомножители степень числа 11 будет заведомо выше одиннадцатой

[@user-bd4jn6cy1k]

@@WildMathing спасибо! Понял.

[@user-fx1pn7en7f]

А задачи вам присылают или вы сами находите себе на свой вкус?

[@WildMathing]

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

[@user-zx1gu4yi6k]

Почему если делится на 80 тоти предыдущие тоже?

[@user-zx1gu4yi6k]

То на

[@WildMathing]

@@user-zx1gu4yi6k, потому что 80²

[@user-yd2qr3qg1u]

А без перебора как решить?

[@WildMathing]

Мы не использовали полный перебор: многие значения отразил для наглядности. В сущности решение состоит из двух шагов. 1) Взяли наименьшее простое число p такое, что p^p>6500, доказали, что оно не удовлетворяет условию. 2) Доказали, что все меньшие натуральные числа удовлетворяют условию. Тем самым получили ответ.

[@anaatlas2758]

Ребят,посоветуете литературу по теории чисел? Что ыб научиться решать похожие задачи и понть основную идею.

[@WildMathing]

Вот здесь немало полезного: kzbin.info/www/bejne/nZm7eneAi8aGY9U

[@valentynmalyi]

128 может

[@AlexX-st3qy]

3:05 6500!=1*2*3*...*6500, каждый третий множитель кратер трем, множителей 6500, т.е. степень тройки как минимум ~2170, что больше 324

[@WildMathing]

Совершенно верно! Точная степень тройки - 3244.

[@AlexX-st3qy]

Просто будучи на олимпиаде я бы наврятли узнал точную степень)

[@jonik_s526]

Найс

[@user-er6zr1tm3i]

Слабо общую задачу решить? Доказать, что для любого натурального N, n = следующее простое число после корня квадратного из N минус единица.

[@WildMathing]

Спасибо за вызов, дружок: всегда мечтаю их получать в таком стиле. Но, к сожалению, твое утверждение неверно даже для N=1.

[@YoutubeBS]

@@WildMathing а что по поводу N≥4?

[@qwitey]

Я так полагаю, что b=[6500/3]+[6500/9]+...+[6500/3^7]

[@napoppym]

По идеи изи

[@user-mn4hg1ql8q]

Ничего не понятно, но очень интересно)

[@user-zi8om1fu4m]

3 часа ночи

[@icecircle201]

ставьте лайк кто решал задачу бинпоиском по простым числам

[@user-er6zr1tm3i]

Верхняя оценка 82; из простых 79, а 83 уже не влезает. Точнее, точно 82.

[@WildMathing]

Можно видео удалять, оставить только твой комментарий!

[@zavenbarikyan596]

Количество троек = 2346861?

[@user-eb6mx5ug2l]

Zaven Barikyan 3244

[@WildMathing]

Все-таки 3244 их. Если правильно понял, твой результат идет от суммы 1+2+3+....+2166. Число 2166, например, - понять можно: количество всех сомножителей кратных трем. А вот за что отвечает слагаемое 2165?

[@vladisami3883]

как дойти до 80?????? я бы сразу не взял 80

[@ohayougozaimasu6424]

80^2=6400, так что сразу очевидно, что ответ не меньше 80.

[@WildMathing]

Можно, конечно, начать с малого, но ведь быстро устаешь и начинаешь думать, до каких пор и на основе чего делимость будет выполнена. Тут уж число 80 возникает само собой.

[@arsenypogosov7206]

Вы не говорите, почему среди чисел кратных 83 в факториале не найдётся числа, которое делится на 83 два раза. А это важно (хоть и просто)!

[@WildMathing]

Чем же я тогда, позвольте, занят в период 3:27 - 3:47?

[@arsenypogosov7206]

Почему сомножителей кратных 83 -- 78 вы объяснили, но, может быть, какое-то из них делится на 83 два раза. (Это как сказать что 9 * 2 не кратно 9, т. к. 3 входит в 9 два раза, а среди множителей только одно делится на 3).

[@WildMathing]

Арсений, смотрите, на 3:32 сказано и даже написано, что число 83 является простым(!), а далее записано то, что [6500/83]=78 - это включает в себя утверждение 83²>6500. Эти два факта дают строгое доказательство того, 83 не подойдет. Если не разберетесь - дайте знать.

[@arsenypogosov7206]

Я с вами согласен, но мне кажется, что стояло пояснить что все множители, кратные 83, не кратны 83². (как вы верно заметили потому что 83²>6500).

[@WildMathing]

​@@arsenypogosov7206, согласен, что это важный факт, но я еще раз пересмотрел ключевые моменты, и убежден, что все получилось хорошо и с точки зрения педагогики (подачи), и с точки зрения математики. На 2:07 в явном виде пишу 6500!, разбивая его на группы, потом на 2:14 показываю (притом с акцентом), как проще и красивее отразить то же самое - с помощью выделения целой части, и далее активно ее использую, всякий раз отражая тем самым, факты вроде 83²>6500. Предлагаю остановиться на том, что оформление - дело вкуса, и нет нужды об этом спорить.

[@rumazius]

Решается в уме за 20 секунд(

[@cesarevitch99]

Как обычно невнимательно прочитал условие и искал просто наибольший k, не учитывая предыдущие значения. P.S. в таком случае k=1008

[@WildMathing]

Бывает! Ты, наверное, имел в виду 1080?

[@MadTavernkeeper]

ахаха, концовка бомба)) не забудьте подписаться на канал, смысл жизни все равно не определен, а так хоть видосики посмотрите)) а если серьезно, то я немного не понял, как проверять факториал на делимость (кроме как посчитать его). Если это простое число - все понятно, на как быть с остальными?

[@MadTavernkeeper]

а, все, разобрался

[@kocyet2441]

Объясните шутку про вставки Григория Перельмана

[@WildMathing]

Никаких шуток: это были серьезные вставки с Григорием Перельманом!

[@EespoLniTel]

Я не знал что есть такие люди, а вы случайно не знаете что такое Сириус

[@WildMathing]

Знаю, конечно: это звезда такая. Ну и центр для одаренных детишек в Сочи, один мой коллега планирует туда устроиться на работу.

[@JayIsStudio]

По совместительству ещё и дядя Гарри Поттыра :D

[@arsenypogosov7206]

Для одарённых детишек и хоккеистов.

[@dl2381]

Сириус Блэк штоле???7?

[@MinecraftForever_l]

в этом видео ни черта не понял....