15 человек обменялись рукопожатиями. Сколько было рукопожатий? Абсолютно эффективная политика

Приветствую.

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

Определения

• Сочетание из k элементов – группа, состоящая из данных k элементов. Для группы неважен порядок расположения элементов. К примеру, группа из двух элементов независимо от порядка расположения (ab и ba) – одна и та же.
• Числом сочетаний из n по k называют количество групп, содержащих k элементов, составленных* из данных n элементов. Число сочетаний равно количеству соответствующих размещений, делённому на k!, так как размещения чувствительны к порядку элементов и потому их в k! раз больше.

Формулы для подсчёта числа размещений и числа сочетаний.

*слово "составленных" относится к слову "групп".

Сочетания VS Размещения: подробнее

• В случае сочетаний группы из трёх элементов: abc, acb, bac, bca, cab, cba – все одни и те же, и любую из 3! записей выше можно использоваться для обращения к сочетанию abc. А в случае размещений – это шесть различных размещений.
• Действительно, выбирая, например, трёх учеников (a,b,c) в качестве дежурных из класса с 15 учениками, нам безынтересно, в каком порядке мы их выберем, нам лишь интересно, кого именно (какую группу) мы выберем. В этом случае ученики a,b,c независимо от порядка их расположения – одна и та же группа (т.е. одно и то же сочетание).
• А вот если мы рассматриваем способы расположения данных 15 учеников на трёх стульях, то порядок их расположения имеет значение, и здесь речь идёт о размещениях, которые чувствительны к порядку расположения элементов (например, abc и bac – не одно и то же, а два разных размещения).

Задача о рукопожатиях

N человек обменялись рукопожатиями (каждый поздоровался со всеми остальными). Сколько было рукопожатий?

Решение

• Каждый поздоровался единожды со всеми остальными. Это значит, что каждый человек из группы из N человек поздоровался с N-1 людьми. Значит, общее число рукопожатий равно N*(N-1), но отметим, что при таком подсчёте число рукопожатий вдвое больше искомого, ведь рукопожатие между людьми А и Б и людьми Б и А одно и то же. Значит N*(N-1) делим на 2 и получаем ответ.
• Видим, что это число действительно совпадает с числом сочетаний из N по два.
• Данная задача имеет красивую иллюстрацию. Изобразим людей в виде вершин на окружности, а их рукопожатия рёбрами (хордами). Получим следующие иллюстрации (графы) для N=6 и N=9.

Хорды на окружности изображают рукопожатия между людьми. В случае встречи шести людей имеем 6*5/2=15 рукопожатий (хорд). В случае встречи 9 людей будет 9*8/2=36 рукопожатий. С точки зрения теории графов указанные выше графы являются полными, а задача о рукопожатиях сводится к подсчёту числа рёбер полного графа, имеющего N вершин.

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

Число людей N=15; а k по-прежнему равно 2. Число рукопожатий будет равно 15*14/2=105. Достаточно много. Хотя так не кажется, ведь при встречах каждый думает преимущественно лишь о своих рукопожатиях.

Изобразим рукопожатия на окружности, построив соответствующий полный граф. Придём к простому выводу: обмен рукопожатиями между людьми куда сложнее и интереснее, чем может показаться на первый взгляд.

Изображение всех 105 рукопожатий хордами на окружности в случае встречи 15 человек.

• Существуют и другие задачи, которые приводят к тем же соображениям: например, задача о количестве партий, сыгранных шахматистами, если каждый сыграл со всеми остальными.
• Также есть задача об эффективной политике: страны наиболее эффективны (при прочих равных) в том случае, когда каждая из них отладила взаимодействие (отношения) со всеми остальными. Общее количество отношений в данном случае также можно подсчитать по выведенной выше формуле (N*(N-1)/2).

Число сочетаний из N по два.

Подписывайтесь на канал. Оставляйте комментарии и лайки. Спасибо за внимание.