Основы комбинаторики и теории чисел 1. Принцип Дирихле. Размещения. Сочетания

Лектор: Райгородский А.М.
Съемка: Бородин Савелий
Монтаж: Овчаренко Кирилл

[@mathand8990]

Райгородский сказал: "Катарсис" - 2 раза; "Кокнуло" - 5 раз; "Кок" - 1 раз.

[@user-it1qb3oi9b]

Значит это настоящий Райгородский

[@Jlight95]

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

[@MrArmas555]

Класс!

[@5elll960]

Меня не просто кокнуло - меня рас3.13д0Rасило во все стороны! А утром получил таки катарсис. Как Андрей Михайлович от таких "катарсисов" до сих пор не седой - не понимаю.

[@weFromRussia]

Если посмотреть количество просмотров этой лекции сейчас - где-то 10 тысяч, но когда я доберусь до последней лекции - интересно будет посмотреть сколько будет просмотров уже там и на тот момент

[@pogart143]

25:00 коротко о математике в непрофильных классах

[@moriarte228]

Может кто-нибудь объяснит на пальцах решение 3 задачи с того места, где используется принцип Дирихле. Я не понимаю, какие тут кроколики и коробки и почему мы делим 1120 на 8. Разве всего 8 коробок?

[@mrilinski]

Вот интересно: сложение n+m вычисляет количество способов выбрать элемент из объединения наборов из n и m элементов, умножение n*m вычисляет количество способов выбрать по элементу из каждого из множеств, возведение в степень n^m вычисляет количество способов выбрать m упорядоченных, но не обязательно различных элементов из множества из n элементов (более строгая и лаконичная формулировка, где множество из m элементов тоже фигурирует - количество отображений из множества из m элементов во множество из n элементов). А существует ли подобное "естественное" определение для тетрации? (Под "естественностью" можно подразумевать, например, то, что это определение не будет переформулировкой индуктивного определения тетрации через возведение в степень, так же явно использующей индукцию. Хотя даже если идти от стандартного определения, всё равно остаётся вопрос - может ли тетрация в принципе пригодиться в комбинаторике?))

[@mrilinski]

Подсказали хоть и не определение, но случай, где тетрация в принципе возникает в комбинаторике: задача определения, является ли граф H минором графа G, для фиксированного H может быть решена в общем случае за время не меньше n^2 * 2^^2^^2^^(h/2), где h - число вершин в H, а n - число вершин в G. В википедии написано здесь: ru.wikipedia.org/wiki/%D0%93%D0%B0%D0%BB%D0%B0%D0%BA%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B9_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC

[@leogame7181]

18:57

[@dmanikhine]

35:35 Не очень внятно показано почему 140 клеток. Возьмем вектор x1,x2,x4,x4 где значения x только -1 или 1. Понятно что таких векторов 16 (2 в четвертой степени). Дальше лектор очень быстро разбивает 16 векторов на 4 группы, таких что в каждой группе скалярное произведение векторов равно 0. Лектор строит первую группу, беря за основу вектор 1,1,1,1. Затем вторую группу умножая векторы из первой группы на -1. Затем берет вектор который не входил в первые две группы. На основе этого вектора строит 3 группу, и умножая 3 группу на -1 получает 4 группу. Исходя из логики построения получили 4 группы. Группы между собой не пересекаются. Всего векторов в 4 группах 16. Все вектора уникальны. Следующий шаг. Расставить 4 элемента (каждый элемент либо -1, либо 1) на 8 позициях можно C из 8 по 4. (70 способов). Для каждого из 70 способов имеем 4 группы. Итого 280 групп. Замечая что для каждой группы есть уникальная группа с ортогональными векторами (Группа x,x,x,x,0,0,0,0 ортогональна группе 0,0,0,0,x,x,x,x), Объединяем эти группы друг с другом. и получаем 140 (280/2) групп в каждой из которых вектора ортогональны друг другу.

[@SiwakSerg]

36:35 - Почему мы уверены, что в каждой "клетке" мы можем разместить по 8 элементов ("кроликов") множества последовательностей таким образом, чтобы внутри ящика всегда две несовпадающие последовательности были ортогональны? Не осознал. Если бы это действительно было возможно, то тогда понятен смысл - берём число "кроликов" последовательностей на единицу большее числа таких "клеток", выясняем, что тогда в одной клетке должно оказаться больше 1-го кролика. Понятно, что x умноженный скалярно на себя даст 4, а не 0. Значит, если в клетке их оказалось 2, а клетка состоит только из ортогональных элементов, то условие на принадлежность множеству W уже не выполнено. Я не осознал только одно, почему из кратности 1120-ти числу 8 следует, что такие 140 клеток вообще будут существовать? Если напихать каких-угодно кроликов, то никакой мажоранты не будет, ибо если окажется хотя бы одна дефектная клетка, то двое кроликов уже могут такой дефектной клетке принадлежать, не опасаясь того, что условие на W не выполнится.

[@SiwakSerg]

Так, я, похоже, догадался до ответа на этот вопрос - Андрей Михайлович построил пример такой "клетки" путём заполнения клетки по одному известному элементу - т.е. если один элемент последовательности известен, то можно узнать все оставшиеся 8 элементов в этой клетке. Это решает вопрос, т.к. больше 8-ми ортогональных элементов для выбранного элемента быть не может, следовательно, одна клетка ставится в соответствие одному своему элементу, а сами клетки при этом не пересекаются. Поэтому из кратности всех имеющихся элементов последовательности числу 8 и следует всё вышесказанное.

[@SiwakSerg]

Хм. То что я написал выше действительно верно. Тогда спрашивается, почему максимальное число элементов не РАВНО 140?

[@SiwakSerg]

Блин, про деффектные коробки перечитал - наличие деффектной коробки даёт право разместить в ней более одного элемента (вектора/последовательности/кролика). Это говорит о том, что оценка, найденная из эмпирической идеи таких коробок, должна быть не верхней, а нижней! А вот рассуждение о построении по одному элементу всех элементов такой коробки говорит уже о разбиении векторов на классы по коробкам. Это приведёт к тому, что это будет ещё и оценка снизу.

[@moriarte228]

@@SiwakSerg что означает выражение, что для выбранного элемента существует не более 8 ортогональных элементов. Разве элементы последовательности могут быть ортогональны? Вообще идея задачи мне так и непонятна. Объясните пожалуйста, я буду вам благодарна)

[@user-hl5hg2lx8o]

Ах ха ха 😂😂😂😂😂😂😂😂0011011011000000000 я поняла! Это видео про то,как вирус мутирует от А до Я ,а потом переходит на алфавит другой страны....потом следующей(а тут уже не смешно