Комбинаторные задачи с ограничениями
  Рассмотрим несколько типов задач, в которых на комбинации накладываются определенные ограничения.
    а) Задача о львах и тиграх. Имеется 5 львов и 4 тигра. Необходимо их расставить в ряд, но при этом известно, что тигр не может идти спокойно зa тигром. Тогда расставляем львов с промежутками ( их будет 6) и в них вставляем тигров. Таким образом, если тигры и львы обезличенные, то         = 15. В общем случае при n львах и k тиграх имеем: 

   б) Задача о книжной полке. Из m книг, стоящих на полке, нужно выбрать k таких, которые не стояли рядом на книжной полке. Отберем сразу k книг, останется n - k. Их расставим с промежутками (n - k+1 промежуток). На эти места вставим k книг. Общее решение:
                                                                                                      (9)
   в) Рыцари короля Артура. 12 рыцарей сидят за круглым столом. Нужно выбрать 5 из них, но таких, которые не сидели рядом за столом. Множество всех решений разбиваем на два подмножества в зависимости от того, входит ли в команду избранных конкретный рыцарь или нет? Ответ: 15 +21 = 36. Если за круглым столом сидит n рыцарей, а нужно выбрать k, которые не сидели рядом, то задача решается аналогично и имеет смысл при 
n > 2k.
     Упражнение
     Определите условия при которых задачи а), б) и в) имеют решения.

Закрыть