Комбинаторика для начинающих - это базовый курс, закладывающий самые основы комбинаторного знания. На этом курсе слушатели, которые почти не знают комбинаторику или прочно ее забыли, откроют ее для себя впервые или заново. Курс очень полезен всем, кому трудно с ходу включиться в продвинутый курс современной комбинаторики. Однако фактические бонусы те же: в итоге человек, прослушавший курс, получит путевку в увлекательный мир комбинаторных задач и их далеко идущих приложений. Более того, даже в нем самом мы уже расскажем об инструментах, позволяющих решать некоторые задачи такой важной прикладной области знаний, как биоинформатика. Курс состоит из 7 учебных недель и экзамена. Каждую неделю слушателю предлагается выполнить тест, составляющий 10% от общей оценки. Экзамен состоит из задач по всему курсу и составляет 30% от общей оценки. Для получения сертификата необходимо набрать не менее 50% от общей суммы баллов. Данный курс является упрощённой версией курса "Современная комбинаторика" и рекомендуется к прохождению перед курсом "Теория вероятностей для начинающих".
Отчёт о школьниках
Loading...
From the course by Moscow Institute of Physics and Technology
Комбинаторика для начинающих
731 оценки
From the lesson
Формула включений и исключений
Как отпраздновать новый год, нарисовать картину Ван Гога, посетить все города России и составить правильный отчёт в школе - в 6-й неделе курса. Формально, мы познакомимся с формулой включений и исключений - очень полезным комбинаторным инструментом. В частности, мы выведем новое тождество и получим формулу для нахождения числа беспорядков.
Meet the Instructors
Дмитрий Ильинскийпреподаватель
кафедра дискретной математики МФТИ
Андрей Райгородскийпрофессор, доктор физико-математических наук
кафедра дискретной математики МФТИ
Так, давайте попробуем теперь с помощью формулы
включения-исключения поискать ошибку в отчете.
Шпаргалку взял, потому что слишком много цифр, наизусть на помню,
напишу неправильно – ошибку не найдем.
Так. В отчете сказано, что в школе, в некоей,
есть 45 учеников,
причем среди этих 45 учеников, в том числе, 25 мальчиков.
Ну, давайте я так и напишу, в том числе в т.ч.,
– это значит «в том числе», 25 мальчиков.
Вполне казенный стиль.
Двадцать пять мальчиков.
При этом известно, что на «хорошо» и «отлично»,
на «хорошо» и «отлично» из вот этих вот 45 учеников учатся 30.
Ну, вообще это не плохо.
Так, на «хорошо» и «отлично»
учатся 30 учеников,
в том числе 16 мальчиков.
В том числе 16 мальчиков.
То есть, вот из 45 человек известно,
что 30 учатся на «хорошо» и «отлично» и, вот среди этих 30,
которые учатся на «хорошо» и «отлично», есть ровно 16 мальчиков.
Кроме того, известно, что спортом занимаются,
и успешно занимаются, спортом занимаются не то чтоб даже известно,
а в отчете сказано, что спортом занимаются 28 учеников,
из вот этих, по-прежнему пресловутых, исходных 45.
Спортом занимаются 28 учеников.
Среди которых 18 мальчиков.
Среди которых – вот среди этих 28 – восемнадцать
мальчиков и 17 учащихся на «хорошо» и «отлично».
И 17 учащихся на
на «хорошо» и «отлично».
То есть, будьте внимательны, вот, известно что,
согласно отчету, 28 есть учеников из 45,
среди которых 18 мальчиков, но вот эти 28 занимаются спортом,
и среди них же, среди этих 28 учеников, 17 товарищей учатся на «хорошо» и «отлично».
Причем, пока не сказано, сколько среди них мальчиков, девочек, – это не сказано.
Так, и наконец, последнее, что известно, это что 15 мальчиков,
вот теперь это будет сказано: 15
мальчиков учатся на «хорошо» и «отлично» и при этом занимаются спортом.
Учатся на «хорошо» и «отлично»,
и при этом занимаются спортом.
Это как раз вот то пересечение, о котором я указывал только что.
Занимаются спортом.
Так вот спрашивается: нет ли в этом отчете какой-нибудь ошибки,
не закралась ли она туда случайно.
Сейчас мы этот вопрос обсудим.
Так, давайте разбираться.
Я на самом деле утверждаю, что скорее всего, закралась ошибка.
Но, глядя на эти данные, сходу понять это невозможно.
Нужно что-то делать.
Ну, давайте попробуем применить формулу включения-исключения,
потому что как-то видно, что здесь даются и количества и их пересечения.
Что-то явно намекает на то, что надо использовать формулу включения-исключения,
– вот явно.
Ну, давайте.
Что такое наши объекты, с которыми мы имеем дело?
a1, ..., a с индексом N, если пользоваться обозначениями с лекции.
Ну понятно, это просто школьники, которые учатся в школе.
Их 45 человек.
Стало быть, N – это и есть 45.
И вот каждый из этих школьников обладает или же не обладает некоторым
перечнем свойств.
Давайте посмотрим, какие в нашем распоряжении имеются свойства.
Ну скажем, что можно считать свойством α1?
Ну наверное, самое первое свойство,
которое здесь явно присутствует в условии задачи – это пол.
Свойство, состоящее в том, что ученик является мальчиком.
Значит, α1 – это свойство, ученик является мальчиком.
Ну или не является мальчиком, тогда он является...
Ой. Друзья мои,
лучше я не буду говорить тогда, кем он является.
Наверное девочкой, все-таки.
Нет? Как вы считаете?
Так. Ну, это скользкий вопрос.
Я понимаю.
Вот. Заполняешь какую-нибудь анкету,
на заграничную визу, например, а там третий вариант дается.
Ни то, ни другое.
Черт знает что, вообще.
Так.
Ну ладно.
Мы не будем в такие дебри вдаваться.
Является мальчиком, не является мальчиком, в конце концов,
ну не является мальчиком и не является, уж кем он там является, может крокодилом.
Так. α2, тоже видно из условия задачи,
какое свойство здесь имеется в виду, α2 – это значит,
ученик учится на «хорошо» или «отлично».
Ученик учится на
«хорошо» и «отлично».
Это второе свойство, которое явно здесь присутствует.
Ну, есть третье свойство – спортом занимается или не занимается.
То есть, α3 – занимается спортом.
И вот про каждого ученика мы в принципе готовы сказать.
Является ли он мальчиком,
учится ли он на «хорошо» и «отлично» и занимается ли он спортом.
Ну, давайте, N мы определили.
N от α1, кажется тоже.
Сколько у нас всего мальчиков?
25, конечно, по условию задачи.
N от α2 – это количество тех учеников, которые учатся на «хорошо» и «отлично».
Ну, прекрасно.
Здесь сказано, это 30.
Ну и надо еще N от α3, наверное, определить.
Это число ребят или там девушек, которые занимаются спортом.
Ну вот, написано, 28 учеников занимаются спортом.
28.
Прекрасно.
Но, поскольку свойств три, то, наверно, бывает еще и одновременное выполнение
этих двух свойств, и даже одновременное выполнение этих трех свойств.
Ну, в нашем условии все есть.
Давайте, например, определим, чему равняется N от α1, α2.
То есть, сколько учеников, одновременно являясь мальчиками, еще, к тому же,
учатся на «хорошо» и «отлично».
Ну вот, смотрите.
Учатся на «хорошо» и «отлично» и в том числе являются мальчиками – 16 человек.
Шестнадцать человек.
N от α1, α3.
N от α1, α3, это значит, мальчик и в то же время занимается спортом.
Ну, смотрим.
Спортом занимается 28 учеников, среди которых 18 мальчиков.
Ну значит, это 18.
Прекрасно.
N от α2, α3 – это что у нас такое?
Это учится на хорошо и отлично и, вместе с тем, занимается спортом.
А, ну прекрасно, спортом занимается 28 учеников,
и из них 17 – на «хорошо» и «отлично».
Значит, здесь мы пишем 17.
И, наконец, для применения формулы включения-исключения
остается вычислить количество пресловутых полиглотов, но в данном случае,
это конечно, тоже никакие не полиглоты, а это просто ребята, которые одновременно
являются, ученики, извините, одновременно являющиеся мальчиками,
учащиеся на «хорошо» и «отлично», и занимающиеся спортом.
Но это 15 человек, нам это в самом конце сказано.
Их достаточно много, таких полиглотов пресловутых.
Тогда количество людей, которые не являются мальчиками,
не учатся на «хорошо» и «отлично», да еще и,
мерзавцы, не занимаются спортом, такие вот отсталые товарищи.
Этих отсталых товарищей, сколько?
Ну формула включения-исключения,
надо написать N − N от α1, − N от α2,
− N от α3 + N от α1,
α2, + N от α1,
α3 + N от α2, α3, ну и наконец,
− N от α1, α2, α3.
Подставляем только что прописанные значения.
У нас получается: 45, общее число людей,
− 25 − 30
− 28 +
16 + 18,
+ 17 и − 15.
Смотрим.
45 − 25 = 20 − 30 = −10
− 28 = −38, + 16 =
−22 + 18 = −4 + 17
= 13 и − 15, ой, это −2.
Оказывается, минус два человека у нас отсталые.
Ну, так не бывает.
Все-таки, количество каких-либо объектов это не отрицательное целое число, но,
как минимум, оно равняется нулю, но отрицательным оно уж никак не может быть.
Противоречие.
Значит, в отчете ошибка.
Таких данных быть не может.
Если бы были такие данные, а мы знаем, что формула включения- исключеня точно верна,
то мы бы получили вот такой нонсенс.
Количество каких-то там людей, которые не являются ни тем-то, ни тем-то,
ни тем-то – оно отрицательное.
Ну вы еще скажите – комплексное число, будет совсем замечательно.
нет, такое невозможно, и значит, в отчет закралась ошибка.
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
