1 задача: алгоритм Евклида,(a, b) = (b, a-b) 2 задача: рассмотрение остатков при делении на 7, решается в 2 действия

В первой задаче Алгоритм Евклида для НОД идеально подходит

@VitalMath

Жыл бұрын

Точно! Можно алгоритмом Евклида

@alterafpga4349

Жыл бұрын

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

@jjjjjjjj296

27 күн бұрын

Тоже так решал

Ооо олимпиады! Я тащилась с геометрии)) найдите площадь поверхности закрашенной фигуры: и только 1 измерение в 6 вписанных объемах)) 3 листа проекций ради однозначного числа в ответе)

В первой задаче легче воспользоваться напрямую алгоритмом поиска наибольшего общего делителя. На первом шагу имеем (21n+4) mod (14m+3) = 7n+1, на втором шагу (14m+3) mod (7n+1) = 1. И всё. Во второй задаче значительно проще рассматривать вычеты по модулю 7 для степеней двойки и доказать что образуется цикл 1, 2, 4. Отсюда и ответ к 1-й задаче - n, кратные 3. И ответ ко 2 задаче - доказательство напрямую следует из того, что в цикле нет числа 6. Третью тоже решил по-другому. Хотя и не скажу что это решение проще авторского. Но зато оно конструктивно в том плане, что по заданному d позволяет определить как можно выбрать числа a и b. Есть три случая: d чётное, d кратно 3, d нечётное и не кратно 3. 1) d - чётное (остаток от деления на 6 равен 0, 2 или 4). d=2n Тогда 2d-1 = 2*2n-1 = 4n - 1. (4n -1) mod 4 = 3. Ни один полный квадрат не может давать остаток 3 при делении на 4. Возможны только остатки 0 (число чётное) или 1 (число нечётное). Значит это не квадрат. 2) d кратно 3. (остаток от деления на 6 равен 0 или 3, хотя 0 мы уже рассмотрели ранее). d=3n Тогда 5d-1 = 5*3n-1 = 15n-1. (15n -1) mod 3 = 2. Ни один полный квадрат не может давать остаток 2 при делении на 3. Возможны только остатки 0 (число кратно 3) или 1 (число не кратно 3). Значит это не квадрат. 3) d не кратно ни 2 ни 3 (остаток от деления на 6 равен 1 или 5) d=6n+1 или d=6n+5 тогда или 13d-1 = 13*(6d+1)-1 = 78d + 12 или 13d-1 = 13*(6d+5)-1 = 78d + 64 Но оба этих числа чётные, а чётное число не может быть квадратом нечётного.

Видос ещё не смотрел, вот мои решения: 1 задача: Выносим целую часть, получаем 1 + (7n+1)/(14n+3). Отбрасываем целую часть и умножааем дробь на два. Все эти действия сократимость не поменяют. А у нас получилось (14n+2)/(14n+3). Несократимая дробь, задача решена. 2 задача: a) Пусть при n=k утверждение верное. Тогда 2^k - 1 = 7*j Выразим 2^(k+1)-1 через j 2^(k) = 7j + 1 2^(k+1) = 14j + 2 2^(k+1)-1 = 14j + 1 2^(k+2)-1 = 28j + 3 2^(k+3)-1 = 56j + 7 Опять делится на 7. Из того, что условие выполняется для k слеудет, что оно не выполняется для k+1 и k+2, но выполняется для k+3 Минимальное n, для которого выполняется, равно 3. Значит по принципу полной математической индукции условие будет выполнятся для 6, 9, 12, 15 и.т.д до бесконечности. Для всех чисел, кратных трём. b) Как понятно из пункта a, 2^n - 1 может иметь остатки 0, 1 и 3 при делении на 7. Следовательно 2^n + 1 может иметь только остатки 2, 3, 5. Доказано.

Молодец, что показывает рассуждения, а не просто дает решения в очищенном виде. Увы, в математике мне часто встречались решения, про которые я не мог сказать, откуда они взялись. Но есть и НО: а почему интересны эти задачи? Я много лет проработал в теоретической физике и почти не встречал хитрых задачек, хитрых кунстштюков, которыми меня в молодости пичкали математики.

Отличное видео! Все почувствовали себя олимпиадниками)

Не проще ли перейти в двоичную систему тогда 2^n-1 = 1111... (n единичек) а 7 = 111 и делить это дело столбиком , тогда ясно будет что оно делится если единичек кратно 3 ( а если не кратно то как раз остатки будут 1 и 11 = 3). а 2^n+1= 100...01 (n-1 - нулей) опять же будет блоками делиться и в конце остаток (10 = 2 либо 11 = 3 либо 101 = 5). да и вообще второй пункт можно не решать так как если в первом случае остатки 0,1 или 3 то во втором случае остатки будут 2,3,5

@user-qq8kp5cw8x

Жыл бұрын

Нет не проще.

@thebishop3588

Жыл бұрын

@@user-qq8kp5cw8x 😀

По первой задаче есть алгоритм Евклида, когда из большего числа вычитается меньшее до тех пор, пока результат не станет меньше или равен меньшему числу. Если результат равен меньшему числу - значит это и есть наибольший общий делитель, если же меньше, значит заменяем большее число на результат и повторяем то же самое с новой парой чисел. Работает это потому, что если исходные числа имеют наибольший общий делитель A, то вычитая одно из другого мы будем получать остаток кратный A, а потому с учётом указанных действий не сможем получить положительное число меньше А. В то же время если оба числа в какой-то момент совпали, и стали равны k, то это значит, что все остальные числа тоже были кратны k, так как если обратить цепочку действий, то получится, что все числа в цепочке действий были получены сложением чисел кратных k. Потому если k не может быть меньше НОД исходных чисел и исходные числа делятся на k, то k и есть НОД этих чисел. Если проделать это с указанным примером, то получим, что НОД равен 1. _________________________ По второй задаче надо рассмотреть 2^n по модулю 7, чему оно бывает равно. а оно равно 2, 4 или 1, при чём циклично (так как после 1 будет снова 2 и весь цикл повторится). Значит в первом случае n = 3k, где k любое целое положительное. Это автоматически доказывает и второй случай, так как 1 может дать 0 только при сложении с -1 (или 6, учитывая, что мы рассматриваем остатки), а 2^n такой остаток при делении на 7 иметь не может ни при каких n. _________________________ Вот третью у меня решить не получилось :( Это причина, почему мне не нравятся задачи, где нет очевидного пути решения (где следующий шаг продиктован не логикой, а основан на допущении, что вот это может подойти). Я точно так же выразил d через квадраты других чисел (что очевидно). Я точно так же начал рассматривать разные остатки (что очевидно), но не зная что искать, я просто в итоге так и не смог прийти к правильному решению, потому что тут нужна была конкретная последовательность действий, которую нужно либо знать, либо просто угадывать, потому что следующее действие никак не вытекает из условий задачи или из предыдущих действий.

А вам такая идея для второй задачи. Если от числа отнять 7, то это никак не повлияет на делимость на 7. Поэтому перейдем от 2^n-1 к 2^n-8. Если n>=3, то можно вынести 8 за скобку и выкинуть, ведь 8 не делится на 7. Тогда останется 2^(n-3)-1. То есть мы вернулись к исходной конструкции, только n стало меньше на 3. Опять отнимем 7 и проделаем такие же действия. Рано или поздно n-3*k станет меньше 3. Ну и тут уж можно перебрать. Нам подходит только n-3*k=0 или n=3*k. Это и есть ответ на первый пункт.

@kollekcionergolov

Жыл бұрын

Блестяще!

@dmitry-ie3vd4ll2z

Жыл бұрын

Модульная арифметика?

Круто 👍

третья задача гораздо быстрее объясняется если сразу сказать что квадрат любого числа сравним с 0 или 1 по модулю 4 и там все сразу становится понятным.. то же самое со степенью двойки - если сразу брать 2 и увидеть в степенях двойки цикл остатков по модулю 7: 2, 4, 1 и затем снова 2, 4, 1.. задачи все в уме эти решаются за 3 секунды.. бывает что на олимпиадах такие задачки включают ради прикола чтоб совсем грустно некоторым участникам не было, но сейчас даже легкие задачки не сравнятся с этими примерами (если говорить хотя бы об уровне краевых олимпиад, не говоря уже про зональные, российские или международные)

Класс👌

Во второй задаче можно просто расмотреть остатки от деления на 7 для 2^n. Обнаруживаем цикл 1, 2, 4. Собственно это и есть ответ и на первый и на второй пункт (есть остаток 1, нет остатка 6)

В задаче 2-б случай 3k рассмотрен с ошибкой - выкладки такие же как в случае 3k+1

Увидел знак олимпиады вначале - начал решать задачу о четырёх цветах на карте 2 задача: не было условия деления нацело, все числа делятся на 7

Хорошие задачи

первую задачу решал так (авторское решение не смотрел): (21n+4)÷(14n+3)=k ; k>1 21n+4=14nk+3k 21n-14nk=3k-4 7n×(3-2k)=3k-4 7n>0 ; (3-2k)0 чего быть не может, что и требовалось доказать😁 так же можно сказать, что при n=1 изначальное выражение равно 25/17, т.е меньше 2; а чтобы выражение стало однажды равным 2, нужно, чтобы при увеличении n числитель рос более чем в 2 раза быстрее знаменателя, а он растёт только в 1.5 быстрее

Спасибо

Третья задача решилась в лоб. 2,5,13-числа Фибоначчи. Взял число не из ряда - 7, и всё сошлось

@user-vx2kh1wf9v

Жыл бұрын

Там фактически надо доказать, что для _любого_ целого положительного дополнительного числа d (кроме 2, 5, 13) найдётся такая пара. Одного примера недостаточно, иначе можно было бы обойтись числом 3, задача оказалась бы слишком простой.

На 8:07 неаккуратно написан бином Ньютона: коэффициент перед третьим слагаемым почему-то (k-1), а не k(k-1)/2

4:04 Модульная арифметика (арифметика вычетов) в помощь.

1ю задачу можно решить с помощью алгоритма Евклида ) 21n+4 14n+3 7n+1 14n+3 7n+1 1 Вывод: числа взаимно простые. Во 2й задаче вторую половину можно было не решать столь заморочно - у нас уже есть возможные остатки для 2ⁿ-1 (0, 1 и 3), достаточно добавить к этим остаткам 2 (разницу между 2ⁿ+1 и 2ⁿ-1) и убедиться, что суммы не делятся на 7.

@VitalMath

Жыл бұрын

Верно!

При просмотре этого разбора печалит только 1 факт, я уже прожал лайк и не могу сделать этого снова

Справедливости ради, все три задачи с весьма старых олимпиад: первая задача c первой IMO, когда с одной стороны только-только прощупывали почву, а с другой стороны, предполагаемые участники были рождены во времена второй мировой войны, поэтому стоит сделать на это скидку, к тому же, задача была явно из слота утешительной. Вторая также предлагалась на очень давней олимпиаде и тоже явно в утешительном слоте. А третья задача не такая уж и простая, парочку нюансов и ложных следов таки имеет, хотя и по меркам межнара ее и можно назвать простоватой. Но она сложнее чем некоторые первые или четвертые задачи из не столь давних лет - по памяти, первая из 2023 и четвертые из 2020 и 2008 попроще будут, из 2023 так вообще халявная даже по сравнению с третьей отсюда.

3 задача. Необходимо рассмотреть остатки по модулю 3. Квадрат любого числа может давать остатки 0 или 1. Рассмотрев остатки d=0,1,2(mod3) получим, что хотя бы в одном из случаев остаток выражения слева (2*d-1, 5*d-1, 13d-1) по модулю 3 равен 2. Значит хотя бы в одном случае a*b-1 не будет являться квадратом целого числа.

Разность степеней с одинаковыми _показателями_ делится на разность оснований степеней. При равных _основаниях_ получается что разность степеней делится на 0 - такое тоже бывает, когда и показатели равны. 😉

У меня задачу 33 получилось понять решение как деление на 7 в восьмеричной системе исчисления. И мне интересно было как школьники это через обычную математику. Оказалось очень красиво. Про остальные смог только по факту найти решение. И кажется так всё просто. Но видно у меня тут как с открытием Америки по факту кажется элементарно.

Задачи классные, последняя решается с помощью оценки сверху и небольшого перебора. Но в школе я бы такую не решил) Половина таких задач решается тут же, если знать, что такое классы вычетов, функция Эйлера и малая теорема Ферма.

На домашнюю задачу подходят числа 2 4 8, но единственное ли это решение, пока не смог доказать

Отличное видео, но у меня остался вопрос. Почему в задаче про множество мы используем информацию из 1 случая во втором? Если найдется хотя бы одна пара, то необязательно, чтобы все случаи одновременно выполнялись.

@user-mw9gk1li1k

Жыл бұрын

А все, я не так прочитал

2:31 откуда взялись 1 и 2?! Перед использованием указателей их надо объявлять!

Вот бы сейчас такие задачи хотя бы на регионе…

@boykissermaths

Жыл бұрын

Сейчас на муниципе задачи сложнее, чем вторая из видео :/

@user-qq8kp5cw8x

Жыл бұрын

@@boykissermaths не соглашусь, но там и правда бывают не простые задачи

@boykissermaths

Жыл бұрын

@@user-qq8kp5cw8x Ну вот в Саратове была задача решить в натуральных числах уравнение 2^n - 1 = 7^m

@boykissermaths

Жыл бұрын

@@user-qq8kp5cw8x понятно, что необходимо доказать неделимость на 7

@user-qq8kp5cw8x

Жыл бұрын

@@boykissermaths под каким номером?

подписался.

клута!

Проще вторую задачу из первого примера решать как первую + 2, что даёт в остатках 2, 3 и 5

Вторая задача элементарно решается если рассмотреть остатки по модулю 7

Na 11:43 i 19:45 oshibochki?

Сколько раз он сказал "четное" и "нечетное"?

Вторая задача в двоичной системе хорошо смотрится...

Ошибка на 11:45. 2^n+1 почему-то равно=2^(3k+1)+1, хотя n=3k !))🤨

Первые две задачи довольно простые для межнара

Это как так одну часть поделили на 2, а другую на 3? Разве так можно?

На продвижение

1:12 Метод Евклида в помощь.

Выражаясь словами классика: нихуя не понял, но очень интересно.

2, 3, 5 Изи

чет условие 3й задачи не понял, можно же легко пример подобрать

@user-lg1el7gz8s

Жыл бұрын

Смысл в том, чтобы доказать что не существует такого числа d, для которого выполнялось бы указанное в задаче условие. Если вы сможете указать d такое, чтобы 2d-1, 5d-1 и 13d-1 были квадратами - то вы нашли контрпример, который тоже является решением задачи. Зачастую, правда, в олимпиадных задачах это либо делается через какие-то хитрые преобразования (потому что контрпример - какой-то нетривильный и дойти до него прямым перебором было бы очень сложно), либо контрпримера не существует вовсе.

Такие задачи в егэ профиль под 18 номером

Третью изи методом мат индукции

Почему число называют не натуральным, а целым положительным? В чем фишка?

@gr33nh0us3-curiosity

Жыл бұрын

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

@YaOlegB

Жыл бұрын

@@gr33nh0us3-curiosity потому что кто-то относит ноль к натуральным, а кто-то нет.

@user-js7fd2ry5v

11 ай бұрын

Я может чего-то не понимаю, но целое это целое, т.е. подразумевается, что может быть дробное. Натуральное дробным быть не может.

Тупость последней задачи в том что достаточно подставить любое число 3,4,6,7 умножить на 2 отнять 1 и вуаля ничего из результата не квадрат. Да хоть число 100.

999 лайков. Не портите пж. Автор закрепи если не поздно

Никогда не понимал, на основании чего на 2:25 вычетают одно уравнение из другого. Никаких объяснений, просто: давайте вычтем. Почему? А можно ли так делать? Почему можно? Со стороны человек похож на мальчика из мультфильма про полтора землекопа. Только мальчик хоть как то рассуждал, а тут даже рассуждения нет, нет объяснения хода мыслей. Что школьник должен понять из этого решения? Что математика непозноваема? Автор мог бы сказать, что мы не просто вычетаем выражение, а уменьшаем и левую и правую часть первого выражения на одно и то же значение. Это понятно, такая математическая операция допустима. Причем в левой части мы уменьшаем на левую часть второго выражения, а правую часть на правую часть второго выражения. Делать это можно потому, что у нас есть это самое второе уравнение, в котором мы написали что обе части равны. А делаем мы это для того чтобы убрать 42n. Вот это будет вменяемое объяснение, а не то что в ролике. Далее про k ничерта не понятно, тоже что-то невнятное сказал что k не может быть больше единицы. Почему не может быть? А хрен его знает. Можно предположить что автор имел в виду, что если k будет больше единицы, например 2 и так далее, то тогда дробь 1/k станет меньше единицы. И тогда она, видимо по мненю автора, будет всегда меньше разности целых чисел. Хотя тут тоже вопрос: смотря какие M и N взять, на них у нас ограничений нет, за исключением того что они натуральные. А коль так, то получать отрицательные значения, чтобы быть меньше 1/2, нельзя. То есть понятие "меньше", о котором говорит автор, это не просто "меньше" на числовой оси. Но автор этого не объясняет и прыгает дальше. Из-за таких объясняторов у нас школьники не могут понять математику, и думают что это мегасложная наука даже на простых задачках.