Задача 2
За круглым столом короля Артура сидят 12 рыцарей. Из них каждый враждует со своими соседями (и только с ними). Надо выбрать 5 рыцарей, чтобы освободить заколдованную принцессу, но среди выбранных рыцарей не должно быть врагов. Сколькими способами это можно сделать?
Решение. Возьмём какого-нибудь рыцаря, скажем сэра Ланселота. Все выбираемые комбинации рыцарей распадаются на два класса — в одних сэр Ланселот участвует, а в других нет. Подсчитаем, сколько комбинаций входит в каждый класс.
Если сэр Ланселот отправляется освобождать заколдованную принцессу, то ни его сосед справа, ни его сосед слева уже не примут участия в этой экспедиции. Остаётся 9 рыцарей, из которых надо выбрать 4 спутников для сэра Ланселота. Так как соседи Ланселота не участвуют в экспедиции, то надо лишь проследить, чтобы среди выбранных 4 рыцарей не было врагов, т.е. чтобы никакие два из них не сидели рядом. Но исключение сэра Ланселота и его двух соседей разрывает цепь рыцарей, и можно считать, что они сидят не за круглым столом, а в один ряд. В этом случае выбрать 4 рыцарей из 9 требуемым способом можно С₆⁴ = 15 способами. Итак, в первый класс входит 15 комбинаций.
Теперь посчитаем, сколько комбинаций входит во второй класс. Так как сэр Ланселот не участвует в экспедиции, то его можно сразу исключить из числа рыцарей круглого стола. А тогда цепь рыцарей разрывается, и остаются 11 рыцарей, расположенных в ряд. Из них нужно выбрать 5 участников экспедиции так, чтобы среди выбранных не было двух, сидящих рядом. Это можно сделать С₇⁵ = 21 способами.
Таким образом, общее число способов равно 15 + 21 = 36.
Ответ: 36-ю способами.