Question

За круглым столом сидят 12 человек. Из них каждый враждует со своими соседями. Сколькими способами можно выбрать 3 человек так, чтобы среди выбранных не было врагов?

Answer 1

Ответ:

Итак, если брать рыцарей через одного то они не будут враждовать, но их будет 6.

из 6-ти можно составить 6 групп по 5,

но есть и вторая половина рыцарей,

их тоже 6 и они не враждуют между собой

из 6-ти можно составить 6 групп по 5

5+5=10

10 способов.

Ответ: 10 способов.

Answer 2

Чтобы выбрать 3 человека так, чтобы среди них не было врагов, нужно учесть, что каждый человек враждует с двумя соседями.

Представим, что круглый стол представляет собой цикл, где каждый человек является вершиной, а враждебные отношения - ребрами. Тогда, чтобы выбрать 3 человека, которые не являются врагами, нужно выбрать 3 вершины так, чтобы между ними не было ребер.

Существует несколько способов решения этой задачи:

1. Метод комбинаторики: - Выбираем первого человека из 12 возможных. - Выбираем второго человека из 9 оставшихся (так как первый человек и его два соседа исключаются). - Выбираем третьего человека из 6 оставшихся (так как второй человек и его два соседа исключаются). - Общее количество способов выбрать 3 человека без врагов: 12 * 9 * 6 = 648 способов.

2. Метод графов: - Строим граф, где каждая вершина соответствует человеку, а ребра - враждебные отношения. - Находим максимальное независимое множество вершин графа, то есть максимальное количество вершин, которые не соединены ребром. - Поиском в графе можно установить, что максимальное независимое множество вершин состоит из 3 вершин. - Общее количество способов выбрать 3 человека без врагов: 3 способа.

Таким образом, существует 648 способов выбрать 3 человека так, чтобы среди них не было врагов.