Комбинаторика для начинающих - это базовый курс, закладывающий самые основы комбинаторного знания. На этом курсе слушатели, которые почти не знают комбинаторику или прочно ее забыли, откроют ее для себя впервые или заново. Курс очень полезен всем, кому трудно с ходу включиться в продвинутый курс современной комбинаторики. Однако фактические бонусы те же: в итоге человек, прослушавший курс, получит путевку в увлекательный мир комбинаторных задач и их далеко идущих приложений. Более того, даже в нем самом мы уже расскажем об инструментах, позволяющих решать некоторые задачи такой важной прикладной области знаний, как биоинформатика. Курс состоит из 7 учебных недель и экзамена. Каждую неделю слушателю предлагается выполнить тест, составляющий 10% от общей оценки. Экзамен состоит из задач по всему курсу и составляет 30% от общей оценки. Для получения сертификата необходимо набрать не менее 50% от общей суммы баллов. Данный курс является упрощённой версией курса "Современная комбинаторика" и рекомендуется к прохождению перед курсом "Теория вероятностей для начинающих".
Пуговицы разных цветов
Loading...
Из курса от партнера Moscow Institute of Physics and Technology
Комбинаторика для начинающих
772 оценки
Из урока
Правило сложения и умножения. Принцип Дирихле
Правило сложения. Правило умножения. Принцип Дирихле.
Познакомьтесь с преподавателями
Дмитрий Ильинскийпреподаватель
кафедра дискретной математики МФТИ
Андрей Райгородскийпрофессор, доктор физико-математических наук
кафедра дискретной математики МФТИ
Давайте еще один пример на принцип Дирихле.
Ну, на самом деле когда мы уже разбирали только что принцип Дирихле, мы видели,
что по большому счету, ну, в общем это рассуждение от противного.
И та задачка, которую мы сейчас разберем, она будет более трудной, немножко,
но в каком- то смысле это тоже будет скорее рассуждение от противного,
чем прямо вот такой вот явный принцип Дирихле.
Итак, есть 101 пуговица
одного из 11 цветов.
Ну, конечно, цветов много, но человеческий
глаз вроде различает большее количество оттенков, так что как-нибудь справимся.
101 пуговица одного из 11 цветов, названия которых я, в общем,
называть не обязан, поэтому все в порядке.
Вот. Утверждается, это утверждение нужно
доказать, что тогда имеет место альтернатива.
Либо найдется 11 пуговиц одного цвета,
либо найдется 11 пуговиц, все цвета которых разные.
То есть у каждой свой уникальный цвет вот из этого множества
из 11 элементов, из 11 цветов.
Давайте это так и сформулируем.
Тогда либо найдется 11
пуговиц одного цвета какого-то, но все одинаковые.
Пуговиц одного цвета либо
найдется 11
пуговиц разного цвета.
Еще раз повторяю, 11 пуговиц разного
цвета- это значит, что каждая из этих пуговиц покрашена в свой уникальный цвет.
Вот среди этих 11 пуговиц присутствуют все имеющиеся в нашем распоряжении 11 цветов.
То есть либо такая полная однородность, полная одноцветность,
либо наоборот полная разноцветность, такая радужность, как иногда говорят,
хотя вы понимаете, что в радуге не 11 цветов, а меньше.
Вот. Ну вот, я это утверждаю.
Я утверждаю, что действительно либо-либо, третьего не дано.
Но смотрите, что значит предположить противное?
Давайте действительно просто действовать методом от противного.
Предположим, что не верно ни это, ни это, что этой альтернативы нет.
Это значит, что верно отрицание этого и отрицание этого.
Я бы так это рассуждал.
Ну давайте, предположим противное, то есть предположим,
что нет 11 пуговиц одного
цвета нет 11 пуговиц одного цвета
ну и нет 11 пуговиц
разного цвета.
И нет 11 пуговиц разного цвета.
Давайте на самом деле прежде всего привяжемся к вот этому предположению.
То есть воспользуемся нашим предположением о том,
что у нас нет 11 пуговиц разного цвета.
Что это значит?
Что значит такое предположение?
Что значит, что нет 11 пуговиц разного цвета?
Это значит, что на самом деле если такое предположение справедливо-
среди вот этих наших 101 пуговиц, среди нашей
101 пуговицы все 11 цветов не задействованы.
Ну если бы все 11 цветов были задействованы,
тогда конечно мы взяли бы просто по представителю из каждого цвета,
взяли бы там красную пуговицу, синюю пуговицу, перламутровую, не знаю,
итого у нас получилось бы 11 пуговиц разного цвета,
и вот это предположение оказалось бы неверным.
Вот давайте отсюда, из этого предположения конечно же следует,
значок следствия нарисуем, отсюда конечно же следует,
что задействовано не более чем 10 цветов.
Так сказать, на покраску наших пуговиц на самом деле на
покраску пуговиц на самом
деле задействованы не более 10 цветов,
то есть какой-то цвет точно не использован, а может быть и несколько.
Не более 10 цветов.
Вот, это вытекает из второго предположения.
Теперь давайте посмотрим на первое предположение.
Первое предположение говорит, что нет 11 пуговиц одного цвета.
Ну то есть по-другому, иначе говоря пуговиц
каждого конкретного цвета не больше 10,
если нету 11 пуговиц какого-либо одного цвета,
то пуговиц каждого конкретного цвета не больше 10.
Ну давайте я вот так красиво подчеркну.
И из этого красивого выведу, как следствие, тоже красивые
стрелочки нарисую, выведу как следствие вот из этого красивого подчеркивания,
что пуговиц каждого
цвета не больше 10.
Ну а теперь смотрите, какое чудо получается.
Задействовано в связи вот с этим не больше 10 цветов на покраску пуговиц.
Не больше 10 цветов.
То есть есть сколько-то пуговиц первого цвета,
есть сколько-то пуговиц второго цвета, и так далее.
Номер последнего цвета не превосходит 10.
Есть сколько-то пуговиц там какого-то цвета,
и вот номер этого какого-то цвета не превосходит 10.
Это вот отсюда следует.
Ну я каждый раз говорю: сколько-то пуговиц первого цвета, сколько-то пуговиц второго
цвета, сколько-то пуговиц последнего цвета, номер которого не превосходит 10.
А сколько?
А сколько написано здесь.
Пуговиц каждого цвета, то есть и первого, и второго, и вот этого последнего,
номер которого не больше 10.
Их самих не больше 10.
То есть вот у нас есть пуговицы, покрашенные первым цветом.
Давайте вот здесь единица- это номер цвета, в который покрашены наши пуговицы.
И этих пуговиц не больше 10 штук.
Вот здесь это написано.
Пуговиц каждого цвета не больше 10, значит и первого тоже.
Дальше есть пуговицы второго цвета и их тоже не больше 10.
И так далее.
А номер последнего цвета, как я уже неоднократно говорил,
сам не превосходит 10.
Ну давайте, энный цвет, и в него покрашено не больше 10 пуговиц.
Ну потому что в каждый цвет покрашено не больше 10 пуговиц.
А n, вот это n, не превосходит 10.
Значит, сколько у нас суммарно получается всего пуговиц в нашем распоряжении?
Не больше 10, не больше 10, не больше 10, и так n раз.
Всего получается пуговиц не больше, чем 10 умножить на n.
При этом n, как я уже сказал, не превосходит 10.
Мы получаем не больше 100.
И это дает нам искомое противоречие, ведь мы-то знаем, что у нас 101 пуговица.
Все, противоречие мы предположили неправильно,
и значит действительно наша альтернатива была справедлива.
Либо найдется 11 пуговиц одного цвета, либо найдется такая вот радужная
раскрасочка, когда все пуговицы разных цветов.
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
