Rivalry2

HTML Diff

0 added 0 removed

Original 2026-01-01

Modified 2026-02-26

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

2 <h2>Принцип голубятни</h2>

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

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

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

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

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

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

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

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

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

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

13 <h2>Элементарные инструменты: двойной счет</h2>

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

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

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

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

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

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

20 7*4=28 заданий, которые студенты должны сделать (минимальное значение) 7*9=63 задания, которые студенты могут сделать вообще (максимальное значение)

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

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

23 28 ≤ x_1 + ... + x_7 ≤ 63

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

25 y_1 + y_2 + ... + y_9 = x_1 + ... + x_7

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

27 28≤y_1 + y_2 + ... + y_9 ≤ 63

28 Нижняя граница достижима, только если хотя бы одно из y_j больше или равно 4 (потому что 9 * 3 = 27 > 28). То есть студенты сдадут экзамен только в том случае, если в бланке есть задания, на которые ответят не менее 4 студентов. На этом доказательство завершено.

29 <h2>Выводы</h2>

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

31 <ul><li>Принцип голубятни - если взять n коробок и положить в них m > n предметов, то по крайней мере один из ящиков должен содержать более одного предмета</li>

32 <li>Двойной счет - два выражения равны, если они являются двумя способами подсчета размера одного и того же множества</li>

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