Комбинаторика для начинающих - это базовый курс, закладывающий самые основы комбинаторного знания. На этом курсе слушатели, которые почти не знают комбинаторику или прочно ее забыли, откроют ее для себя впервые или заново. Курс очень полезен всем, кому трудно с ходу включиться в продвинутый курс современной комбинаторики. Однако фактические бонусы те же: в итоге человек, прослушавший курс, получит путевку в увлекательный мир комбинаторных задач и их далеко идущих приложений. Более того, даже в нем самом мы уже расскажем об инструментах, позволяющих решать некоторые задачи такой важной прикладной области знаний, как биоинформатика. Курс состоит из 7 учебных недель и экзамена. Каждую неделю слушателю предлагается выполнить тест, составляющий 10% от общей оценки. Экзамен состоит из задач по всему курсу и составляет 30% от общей оценки. Для получения сертификата необходимо набрать не менее 50% от общей суммы баллов. Данный курс является упрощённой версией курса "Современная комбинаторика" и рекомендуется к прохождению перед курсом "Теория вероятностей для начинающих".
Художники
Loading...
来自 Moscow Institute of Physics and Technology 的课程
Комбинаторика для начинающих
712 个评分
从本节课中
Формула включений и исключений
Как отпраздновать новый год, нарисовать картину Ван Гога, посетить все города России и составить правильный отчёт в школе - в 6-й неделе курса. Формально, мы познакомимся с формулой включений и исключений - очень полезным комбинаторным инструментом. В частности, мы выведем новое тождество и получим формулу для нахождения числа беспорядков.
与讲师见面
Дмитрий Ильинскийпреподаватель
кафедра дискретной математики МФТИ
Андрей Райгородскийпрофессор, доктор физико-математических наук
кафедра дискретной математики МФТИ
Давайте разберём ещё один вариант формулы включений-исключений, который,
строго говоря, на лекции доказан не был, но интуитивно,
я думаю, что будет совершенно понятен.
Вот такая вот задача.
Была некая картина Ван Гога.
Ну она и есть, собственно говоря,
и три художника
современных, которые независимо друг от друга,
никак не сговариваясь, решили эту картину перерисовать.
Ну понятно,
перерисовать картину великого художника — это требует больших усилий, времени.
Вот они какое-то время поперерисовывали, часть картины у каждого нарисовалась,
но полностью картину никто из них, вообще говоря, не произвёл.
Вот давайте предположим, что эти три художника встретились в тот момент,
когда у каждого из них перерисованной оказалась ну, например,
больше, чем две трети от исходной картины Ван Гога.
Так ну давайте это запишем: художники встретились [ПИШЕТ
НА ДОСКЕ] случайно, если хотите,
когда у каждого из них [ПИШЕТ
НА ДОСКЕ] было готово более, чем две трети картины.
Ну не менее двух третей.
Было готово не менее двух третей картины.
Чтобы быть совершенно понятным,
давайте я оговорюсь так: имеется ввиду, что по площади.
То есть, вообще говоря, перерисовывать они могли как угодно по-китайски, по-дурацки.
То есть они могли ляпнуть отсюда кусочек, отсюда кусочек, отсюда кусочек.
Важно только, чтобы суммарно от площади картины каждый из них перерисовал не
менее, чем две трети, — долю размера: две трети.
Не менее, чем две трети картины.
При этом общая картина может и не вырисовываться.
Он там какие-то отдельные кусочки странным образом нарисовал, намалевал.
Получилась какая-то бяка, не похожая на Ван Гога,
но вот две трети картины перерисовал как минимум.
Спрашивается, может ли такое быть, может ли так быть,
что, при этом у каждых двух из них,
что, при этом у каждых,
давайте двоих художников общая
часть нарисованного,
общая часть нарисованного
[ПИШЕТ НА ДОСКЕ]
составляет не
более одной четверти исходной картины.
[ПИШЕТ НА ДОСКЕ] Ну давайте разбираться.
Что это вообще всё означает?
Я бы нарисовал вот такую вот вспомогательную картину.
Я, конечно, не мастак нарисовать картину Ван Гога.
Ну условно давайте считать, что вот этот прямоугольник, — это картина Ван Гога,
там что-то нарисовано всюду, и вот первый художник нарисовал там
какой-то вот такой значительный кусок, назовём его A1.
Я ещё красиво нарисовал, в том смысле, что это кусок такой связный он,
не разорванный, а мог бы нарисовать разорванный, например, вот как-нибудь так.
Здесь какая-то бяка и отдельно ещё какая-то бяка.
Вот мы их так сейчас заштрихуем, и то,
что заштриховано, — это будет называться всё вместе A2.
Вот это вот — это A2, это кусок картины Ван Гога,
который к настоящему времени успел пририсовать второй художник.
Ну и, наконец, надо ещё как-нибудь изобразить,
ну A2 маленькое какое-то получилось.
Мы же знаем, что это две трети от общей картины.
Ладно, сейчас я ещё добавлю какой-то такой.
Опа!
Вот такую вот сарделечку и её тоже заштрихуем.
Вот. Вот теперь уже как-то более или менее
похоже на то, что две трети картины исходной картины Ван Гога второй художник
тоже успел нарисовать.
Ну я уж, наверное, не смогу сюда приляпать на эту картинку A3.
Ну есть ещё какое-то множество точек, на самом деле, вот на этой картине, которая
обозначается A3, и это то самое множество, которое нарисовал третий художник.
Вот он нарисовал кусок картины, который мы обозначаем A3.
Так, ну давайте напишем вариант формулы включения исключений,
который формально не следует, конечно, из теоремы, доказанной на лекции, но,
тем не менее является правильным, если строго понимать, что такое площадь.
Давайте модулем множества просто обозначим площадь этого множества.
Модулем множества точек на картине обозначим площадь этого множества, считая,
что площадь можно вычислить, и попробуем понять,
как устроена площадь объединения трёх кусков, намалёванных нашими художниками.
Есть кусок A1, есть кусок A2, есть кусок A3,
— вместе они составляют какую-то часть исходной картины.
Давайте знаете что?
Давайте считать, что исходная картина, — без ограничения общности, как говорят,
имеет площадь 1.
Просто площадь 1.
Мы так отнормировали площадь, чтобы площадь всей исходной картины равнялась 1.
Тогда удобнее просто записывать выражения,
не таскать за собой лишние какие-то делители что ли.
Ну чему же равна площадь объединения этих кусочков?
Ясно, что надо посчитать площадь кусочка A1,
прибавить к ней площадь кусочка A2, прибавить площадь кусочка A3.
Дальше вычесть то, что лишний раз прибавили,
то есть вычесть общую часть A1 A2,
вычесть общую часть A1 A3,
и, наконец, общую часть A2 A3.
Ну и самое последнее, что надо сделать, это прибавить то, что лишний раз вычли,
а именно: прибавить общую часть всех трёх кусков.
Теперь давайте смотреть, какие у нас условия даны, — это в точности формула
включения исключений, просто переписанная не для конечного множества объектов,
а для бесконечного, на самом деле, мы как бы говорим, что каждая точка,
на картине Ван Гога обладает некоторым свойством, а именно: свойством α1,
если она принадлежит множеству A1, а свойством α2, если
она принадлежит множеству A2 и свойством α3, если она принадлежит множеству A3.
Конечно, точек бесконечно много, но вот это я уж доказывать не буду.
Формула, конечно, интуитивно понятно, что верна.
Но мы не знаем строгого определения площади,
поэтому рассуждаем скорее в интуитивных терминах.
Смотрите, мы что знаем.
Мы знаем, что A1 имеет площадь не меньшую двух третей.
Двух третей от всей картины, но вся картина у нас, мы договорились, имеет
площадь 1, поэтому давайте эту сумму всю вместе оценим как 3 умножить на две трети.
Каждая площадь, которая здесь написана в качестве слагаемого,
она ведь по условию не меньше двух третей.
И таких площадей три штуки.
Дальше.
А спрашивается, может ли так быть, что при этом у каждых двоих художников
общая часть нарисованного составляет не больше одной четверти.
Ну давайте предположим, что такое случилось.
Давайте предположим,
что каждое из вот этих пересечений-таки не превосходит одной четверти.
Ведь ровно это здесь написано.
Предполагается, что и вот это пересечение имеет площадь не больше четверти,
и вот это, и вот это, но раз не больше, то со знаком минус, больше либо равно.
Всё опять сводится к тому знаку, который у нас здесь написан.
минус трижды.
Трижды, потому что 3 знака минус, умножить на одну четверть.
Ну а, знаете ли, вот эту вот площадь мы возьмём и просто оценим нулём снизу.
Понятно, что любая площадь не меньше 0.
Может они вообще не пересекаются?
Пожалуйста, тогда будет 0, но отрицательной площадь не бывает.
Поэтому больше либо равно трижды две третьих,
минус трижды одна четверть, ну и +0, а 0 — он и в Африке 0.
Получаем: трижды две третьих — это 2 минус трижды одна четверть — это три четверти,
это больше, строго, чем 1 и это нонсенс, потому что площадь объединения,
ну она точно не превосходит площади всей картины, которая = 1.
Площадь объединения точно не больше 1,
потому что всё это объединение целиком содержится в картине площади 1.
А мы, предположив вот это, получили что?
Больше 1 противоречие, и значит такого не может быть.
