Зарегистрируйтесь для доступа к 15+ бесплатным курсам по программированию с тренажером

Элементарные инструменты Комбинаторика

eyJpZCI6IjRkN2U4NzljMGQ2NzQxMDE3NDlmZWZjZDc5YWZkNGE3LnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=6d44f07d34341bebe391566323a9536f58507bd9554ff4d616cd811bcf26c463

Как и в любом другом разделе математики, в комбинаторике есть свои элементарные инструменты — они помогают решать задачи и упрощать сложные выражения. В этом уроке мы изучим два базовых инструмента — принцип голубятни и двойной счет.

Принцип голубятни

Принцип голубятни или принцип Дирихле — это комбинаторное правило, которое можно сформулировать так:

Возьмем коробок и разложим по ним предметов. По крайней мере один из ящиков должен содержать более одного предмета при условии, что

Свое название правило получило от знаменитого примера с голубями. Его привел математик Петер Дирихле:

Если построить голубятню на мест и поселить в нее голубей, то как минимум одно место будет занято несколькими голубями

Согласно этому принципу, если объектов (голубей) разместить в коробок, то хотя бы одна коробка будет содержать объектов. Так это выглядит на примере с голубями:

eyJpZCI6ImQ5MjE1NjFjNDkxNDYwMDQwOTgxODdkNjhmMzFkMDIxLnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=1737579bedec644ea8ee9506b7c57cc1588789170494c2af4ad9980a78b4f0c3

Этот же принцип можно использовать в другом интересном примере:

В толпе из человек найдется как минимум два человека с одинаковым днем рождения

Чтобы доказать эту мысль, применим принцип голубятни. В примере выше есть 367 человек и только возможных дней в году (с учетом високосного года). Дней меньше, чем людей — то есть не всем людям достанется уникальный день рождения. Поэтому по крайней мере два человека будут с одинаковым днем рождения.

Возьмем похожий пример. Представим колледж, в котором нужно провести уроков за доступных слотов в расписании. Как выяснить минимальное количество кабинетов для этой задачи? Нужно разделить уроков на доступных слотов — получится . Округлим до кабинетов, чтобы не столкнуться с ситуацией, когда приходится проводить два урока в одном кабинете.

В курсе мы разберем еще множество задач и увидим, как принцип голубятни помогает в решении простых задач и заметно упрощает работу над сложными.

Элементарные инструменты: двойной счет

«Двойной счет» или «счет двумя способами» — это комбинаторная техника, с помощью которой можно доказать равенство двух выражений. Само правило можно сформулировать так:

Два выражения равны, если они являются двумя способами подсчета размера одного и того же множества

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

Разберем на примере:

Представим, что мы проводим экзамен и раздаем студентам бланки с заданиями. Каждый студент должен выполнить не менее заданий. Как доказать, что есть хотя бы одно задание, которое выполнили не менее учеников?

Для начала определим недостающие значения:

заданий, которые студенты должны сделать (минимальное значение)
задания, которые студенты могут сделать вообще (максимальное значение)

Чтобы решить задание, применим двойной счет.

Первый способ: Подсчитаем общее количество заданий, выполненных каждым из студентов. Количество выполненных заданий обозначим через :

Второй способ: Подсчитаем, сколько студентов решили задачу номер , и так далее. Если — это количество студентов, решивших задание, то общее количество выполненных заданий обозначается так:

Из этого равенства делаем вывод:

Нижняя граница достижима, только если хотя бы одно из больше или равно (потому что ). То есть студенты сдадут экзамен только в том случае, если в бланке есть задания, на которые ответят не менее студентов. На этом доказательство завершено.

Выводы

В этом уроке мы познакомились с двумя базовыми инструментами комбинаторики:

  • Принцип голубятни — если взять коробок и положить в них предметов, то по крайней мере один из ящиков должен содержать более одного предмета

  • Двойной счет — два выражения равны, если они являются двумя способами подсчета размера одного и того же множества

Эти принципы помогут вам решать простые комбинаторные задачи и упрощать решения в более сложных случаях.


Аватары экспертов Хекслета

Остались вопросы? Задайте их в разделе «Обсуждение»

Вам ответят команда поддержки Хекслета или другие студенты

Об обучении на Хекслете

Для полного доступа к курсу нужен базовый план

Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.

Получить доступ
1000
упражнений
2000+
часов теории
3200
тестов

Открыть доступ

Курсы программирования для новичков и опытных разработчиков. Начните обучение бесплатно

  • 130 курсов, 2000+ часов теории
  • 1000 практических заданий в браузере
  • 360 000 студентов
Отправляя форму, вы принимаете «Соглашение об обработке персональных данных» и условия «Оферты», а также соглашаетесь с «Условиями использования»

Наши выпускники работают в компаниях:

Логотип компании Альфа Банк
Логотип компании Aviasales
Логотип компании Yandex
Логотип компании Tinkoff

Используйте Хекслет по-максимуму!

  • Задавайте вопросы по уроку
  • Проверяйте знания в квизах
  • Проходите практику прямо в браузере
  • Отслеживайте свой прогресс

Зарегистрируйтесь или войдите в свой аккаунт

Отправляя форму, вы принимаете «Соглашение об обработке персональных данных» и условия «Оферты», а также соглашаетесь с «Условиями использования»