Зацикливание и шаг назад - Юрий Маркелов и Алексей Савватеев

[@MishaCasper]

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

[@YuriiMarkelov]

На каком моменте Вы перестали понимать?

[@ДмитрийГитман]

@@YuriiMarkelov что по принципу дирихле повторилось?

[@proglife3936]

@@ДмитрийГитман ну тут нужно просто понимать сколько наборов чисел существует вида (a,b) после деления самих чисел по модулю n. очевидно, что на первой позиции может стоять любое число от 0 до n-1 и на второй позиции аналогично, соответственно всего n^2 вариантов таких пар, учитывая порядок, ну и понятно, что через n^2 таких пар уникальных точно не останется и возникнет повторение.

[@nikolaymatveychuk6145]

По задаче с дорогами: Как Алексей верно подметил, эту систему дорог можно представить как лабиринт. Тогда такое следование по лабиринту равносильно перемещению по нему не отрывая левой руки от левой стены. Так, как тупиков по условию задачи нет, то когда-то мы обязательно попадём в цикл и начнём ходить по кругу вдоль той самой стены (количество перекрёстков конечно, а без тупиков мы ходить можем бесконечно долго, а значит когда-то попадём в точку, в которой уже были). И не попасть в исходную точку мы могли бы только в том случае, если бы в точку, в которой начинается цикл, можно было бы попасть двумя дорогами (чтобы по одной в цикл прийти, а по другой ходить в самом цикле). Но следование вдоль стены гарантирует единственность пути, а значит возвращение в замок неизбежно. По задаче с кубиками: Если для какого-то кубика в верхнем слое не выполняется указанное правило, то в следующем слое мы его заменяем на противоположный, а если выполняется, то оставляем таким же. При этом взяв любых 2 соседних слоя такой башни её можно однозначно восстановить до самого низа, следовательно, если при таком построении образовывается цикл из-за которого башня становится бесконечной, то это должен быть обязательно цикл, начинающийся от подножья башни (так как к любой паре слоёв можно прийти лишь единственным образом). Но под первым слоем ничего не было и такой цикл возможен только в том случае, если последний слой цикла будет равен первому (иначе цикл не получился бы, потому что для некоторых из кубиков поменялась бы чётность), но 2 одинаковых подряд идущих слоя означают, что первый из них был "укомплектован" правильно и на нём башня должна была закончиться. Следовательно это доказывает, что в этой башне невозможны циклы, а потому каким бы не был первый слой, всегда можно построить башню конечной высоты по указанным правилам.

[@YuriiMarkelov]

Да, все правильно.

[@stetig1]

Побольше хочу видео о разных олимпиадных методах

[@programmingwith9064]

Про тридевятое царство - аналогично рассмотренным задачам, при условии что число замков конечно, а перекрестков типа виадуков не бывают (ибо при несоблюдении этих условий тривиально строятся контрпримеры), приходим к тому, что граф дорог планарный и в конечном счете мы попадем в вершину, в которой уже были (т.к. их конечное число). Допустим, это не стартовая вершина. Тогда мы в нее попали 2-мя путями: по ребру на пути от стартовой (назовем его а), и по ребру на пути получившегося цикла (назовем его б). Но это противоречие, ибо тогда попав в эту вершину первый раз по ребру а мы по правилу левой руки должны были выйти по ребру б (т.к. граф планарный, это можно считать интуитивно очевидным, хотя согласен, здесь Бурбаки бы докопались )))) Итого цикл есть, замкнуть его на любую вершину кроме стартовой не можем -> замыкается на стартовую

[@YuriiMarkelov]

Верное доказательство.

[@romanetslov]

Решил пересмотреть после нового матбоя)

[@NadiraShoketayeva]

2. для каждой пары слоев можно однозначно определить последующий и предыдущий, так как новый слой помогаеть дополнить ровно по одному соседу. это значит, что возможен либо полный цикл слоев, либо как раз законченная башня. в цикле мы когда-нибудь придем к ситуации An -> A0(изначально данный слой) - А1. Но так как слой А0 полностью доплняется слоем А1, слой Аn == A0, а значит цикл в этом месте можно разорвать и получить нормальную башню.

[@YuriiMarkelov]

Правильно

[@Anna_Helena_Wiertinska]

Я технарь, а не математик, но мне невероятно интересно. Спасибо!!!

[@YuriiMarkelov]

Спасибо.

[@mrilinski]

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

[@YuriiMarkelov]

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

[@mrilinski]

@@YuriiMarkelov Ура.

[@NadiraShoketayeva]

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

[@YuriiMarkelov]

Абсолютно верно.

[@tetnit6485]

Конечно же 3 в 9 ой! Конечно на земле такого нет, это же сказочное царство👑🧚‍♀️ Молодец!😁

[@РусланМаркевич-ы7о]

я так себе в математики , но ваше видео люблю. так держать!

[@ПавелКуликов-м9м]

По задаче про Ивана - а)комментарий Савватеева, что 3*9=27 упомянут ещё в известной песне Высоцкого, собственно по этой строчке ее можно найти, и оценить актуальность. б) условие, что в системе дорог и замков нет тупиков кажется лишним, если я не прав достаточно одного контрпримера, буду признателен. По собянинской задаче - для технарей и любителей стоит наверное лишний раз упомянуть что 0 - четное число, соседи считаются по граням, и все такие элементарные мелочи..

[@АндрейАлёшин-ы1ы]

Как говорил наш тренер по физике: "Все математики жулики"

[@ДмитрийЗахаров-у5х6е]

Задачу про полоски я узнал от Канеля, она очень любит ее давать. Приведенное решение можно переговорить так: сопоставим шаблону из клеток понятно какой многочлен по модулю 2 и будем на него делить с остатком многочлены вида x^n. Какие-то остатки совпадут, поэтому соответствующая разность x^n-x^m делится на наш многочлен, а это равносильно задаче. Вот более интересный пункт "б" этой задачи: дан шаблон на клетчатой плоскости, обязательно ли его можно понакладывать (по тем же правилам, что и в исходной задаче) так, чтобы осталось меньше миллиона и больше нуля черных клеток?

[@alexeyzabashta]

По второй задаче: Закодируем каждый этаж латинской буквой. 1) Мы всегда можем построить новый этаж, чтобы сделать корректным состояние предыдущего, причём новый этаж сам может быть не корректным, но мы его тоже починим следующим (если надо). 2) Каждый новый этаж единственным образом определяется двумя предыдущими. И наоборот по текущиму и предыдущему можно определить предпредыдущий. 3) Если над очередным этажом мы хотим построить его же ...XY -> Y , значит текущая последовательность этажей ...XY уже была корректной и новый строить не надо. Это следует из факта, что если мы строим над чёрной клеткой чёрную, значит у нижней клетки нужная чётность белых клеток и наоборот. 4) Из 2 и 3 следует, что мы можем приравнять нулевой этаж к первому (который нам дали). 5) Число различных этажей конечно. Значит, если мы не можем построить башню конечной высоты, то только в случае, когда последовательность этажей зациклилась. 6) Из 5 следует, что плохая последовательность должна выглядеть, как AABCDEFG(HDEFG), 7) Из 2 следует, что H = C, G = B и вообще вся последовательность должная являться циклом. 8) Из 7 следует, что цикл будет содержать подстроку AA. 9) Из 3 следует, что мы можем отрезать от этой бесконечной последовательности, корректную конечную последовательность. Следовательно башню всегда можно построить. Забавно, что если посмотреть на высоты этих башен для квадратных оснований n x n, то получится безумная последовательность: 3, 3, 6, 6, 30, 12, 63, 12, 126, 60, 1023, 24, 4095, 126, 510, 24, 510....

[@YuriiMarkelov]

Правильное и очень четко расписанное решение.

[@NadiraShoketayeva]

почему вы предполагаете в п6, что последовательность ААВС* правильная? откуда предположение, что нулевой этаж заполнен по правилам?

[@NadiraShoketayeva]

а, я поняла. в п6 вы, наверное, имели в виду, что вы и вниз строите бесконечную зацикленную башню?

[@lesnoyzhitel4315]

Отличное видео молодец пацанчик. Есть такое небольшое пожелание расскажите если возможно про доказательство Дона Загира теоремы о сумме квадратов натуральных чисел...

[@YuriiMarkelov]

Спасибо.

[@olegvertual6787]

Крутое видео

[@YuriiMarkelov]

Спасибо

[@isafinllr9840]

большое

[@waldemarmoskalecki7891]

1:10 у перестроечного поколения выражение "эти... кролики" вызывает совсем другие ассоциации, нежели мысли о числах Фибоначчи. Я сразу подумал об известных артистах-юмористах

[@yevhenii0]

оо, марик)))

[@mikhailkonovalov7446]

Последнее время кажется что все больше Саватеев снимает для математиков оунли.

[@ЖонХолкинмен]

чуувак видно авторитетный , а что за сборная какой вид спорта?

[@Андрей-Цыбульников]

Мат.олимп сборная полагаю ))

[@YuriiMarkelov]

Сборная Москвы на Всероссийской олимпиаде школьников по математике.

[@vitekpm]

Очень не понравилось, что Алексей Владимирович часто перебивал Юру. Юра всё аккуратно и обстоятельно рассказывает, а Алексей Владимирович на каком-нибудь важном шаге вклинивается в стиле "я всё понял, мне всё понятно, тут дальше всё очевидно". Уж если пригласили гостя, то дайте возможность ему рассказать задачи так, как он хочет и не перебивайте посреди рассуждения. Встречаются замечания по делу, но часто это просто "я уже всё понял, но ты продолжай", "ёкарный бабай, ничего себе". Есть фрагменты решения, которые Юра и так произносит, но Алексею Владимировичу, как будто, принципиально показать, что он уже сообразил, и перебить Юру. После рассказа решения полностью - комментируйте на здоровье. А так, как происходит у Вас, смотрится не очень красиво.

[@Itoyokofan]

Тем более, что главное чтобы не Алексей, а зритель понял.

[@nurlybekmoldagaliev8920]

К задаче с кубиками. Если основанием "башни" является единственный чёрный кубик (площадка 1x1), то "здание" будет одноэтажным🥴 Для белого основания 1x1 получим трехэтажку.

[@YuriiMarkelov]

А для других оснований? Посмотрите условие задачи в описании.

[@stetig1]

а интересно, кстати, можно ли по индукции дальше

[@ЭдуардМалх]

Уважаемый Алексей! Не пишите, пожалуйста, зелёным маркером! Он почти не читается на такой крупности!!!

[@ПепелПтичий]

Очень приятно лицезреть Маркелова младшего на этом канале. Жаль, что Юра не пожонглировал в конце. Все видео ждал. А так, Юре респект.

[@YuriiMarkelov]

Спасибо.

[@vadimromansky8235]

Ух ты, вы там гипотезу колаца во второй задаче не доказали?

[@YuriiMarkelov]

К сожалению нет, мы не доказали Гипотезу Коллатца. Но они чем-то действительно похожи.

[@Oksana_Vrublevskaya]

А сколько Юре лет? А откуда такие одарённые дети берутся? 😜 Скажите, а языки им легко даются?

[@Маткульт-приветАлексейСавватее]

Юрка на год старше моего старшего, кажется. То есть, 16-17 лет. Одарённые детки берутся известно откуда, откуда и все остальные :-))), но обычно это свойства, заложенные Папой и выращенные с любовью Мамой :-)). Иногда, может быть, и наоборот :-))))))! Про языки ХЗ

[@stetig1]

это труд родителей и учителей. надо заниматься детьми

[@trubokur4783]

Вот же я тупой

[@НикитаБаженов-э9о]

Еще есть время всё исправить

[@онименноон-ц9ж]

@@НикитаБаженов-э9о лоботомия?

[@БешенныйАпельсин-ш3э]

Это не страшно, разница между самым умным гением и самым тупым критичном укладывается в погрешность измерений. Если сравнивать с сильным искусственным интеллектом. То есть с его точки зрения все люди тупые.

[@БешенныйАпельсин-ш3э]

гений В одиночку тоже ничего не сделает. Я иногда думаю, что тупым быть лучше. Вон животным ничего не надо, и проблем у них нет. Живут, вполне успешно и самостоятельно в дикой природе. А, весь такой умный и разумный человек, чем больше развивает цивилизацию, тем больше создаёт себе проблем.