Денис Борисов
апрель 2016.
181

Стал интересоваться вопросом равенства P и NP. Почему, в качестве примера, прибегают к задаче с расселением студентов, если, по сути, там не 400^100 комбинаций?

Ответить
Ответить
Комментировать
7
Подписаться
1
1 ответ
Поделиться

В этой задаче, действительно, не 400^100 комбинаций. Не знаю, где Вы нашли такой ответ.

Количество способов, которыми можно расселить 400 студентов по 100 местам, вообще говоря, зависит от вместимости комнат, то есть от того, сколько есть одноместных, двухместных и так далее комнат.

Предположим для простоты, что все комнаты одноместные. Тогда количество комбинаций равно 400×399×...×301 = 400!/300! (сначала выбор из 400 студентов, потом из 399 и так далее).

В общем случае, если у нас n студентов и m мест, k₁, k₂, ... - количества k-местных комнат, количество комбинаций будет равно n!/(m!×(2!×k₂)×(3!×k₃)×...×(r!×kᵣ)), где r - максимальная вместимость.

Заметим, что даже в лучшем случае (одна 100-местная комната), количество комбинаций равно 400!/(300!×100!), что больше предполагаемого числа атомов во вселенной.

3

Я рассматривал задачу не со стороны способов возможных вариантов для расселения, а с плана совместимости студентов. Да, кол-во способов расселить 100 студентов по 100 комнатам равна 100!. Но Зачем нам эти условности? Если мы будем рассматривать задачу, откидывая все возможные способы расселения студентов по комнатам, то вариантов проходящих по совместимости студентов будет не так много. В силу своей невероятной глупости я не смог придумать быстрый способ посчитать все комбинации совместимости студентов. Но я упростил задачу и у меня получилось, что если выбор идет из 10 студентов, двух из которых стоит заселить, то всего есть 45 вариантов их возможной совместимости.

0
Ответить

Вариантов, проходящих по совместимости действительно будет не так много. Наша задача - найти хотя бы один. Если P!=NP, то иначе, как каким-то перебором всех вариантов, мы этого сделать не сможем...

+1
Ответить

Дело даже не в том. Я упрощаю себе задачу: Допустим есть 400 студентов, двух из которых мне нужно поселить по предмету совместимости.  Как будет выглядеть формула мною выведенная для подсчета всех возможных вариантов комбинации двух студентов из 400? Я делаю все "грубо" Допустим мы совмещаем студента №1 с каждым студентом от №2 до №400 получится 399 пар студентов, которые будут иметь в себе студента №1. Далее студент №2. Нам нужно создать с ним пары, но так как пара со студентом №1 была в предыдущем подсчете начинаем со студента №3 и до №400. Далее №3. Совмещение со студентом №1 было в первом перечислении, со студентом №2 во втором, значит начинаем с №4 и до №400. По этой логике каждый новый подсчет пар будет иметь на 1 пару меньше, то есть если стоит задача посчитать все возможные пары из 400 студентов формула будет такая: 399+398+397+396+(предыдущее число - 1)...+1=количество всех возможных пар из 400 студентов.

0
Ответить
Ещё 3 комментария

Как по мне, по такой же логике можно посчитать все возможные сотки из 400 студентов. Факториал будет использоваться в том случае, если мы помимо студентов будем менять их перестановку. Но ведь перестановка нас не существенна, поэтому факториалы, как я считаю, использовать не стоит. (я могу быть и не прав, но пока я не могу понять, в чем суть) 

0
Ответить

Число таких соток - биномиальный коэффицент. Он будет равен 400!/(100! * 300!) - рассмотрим все перестановки студентов и скажем, что мы поселим первую сотню, а оставшихся не поселим. Поэтому разделим на 100! и 300! - порядок студентов внутри этих групп не значим. Если вам интересно, точное число: 2241854791554337561923210387201698554845411177476295990399942258896013007429693894018935107174320. 

+1
Ответить

Действительно...

Получается, это правда. То есть для моего случая... Если есть 400 студентов и 2 нужно заселить, то 399+398+397+396...+1=400!/(2!*398!). Очень интересно. Спасибо

0
Ответить
Прокомментировать
Ответить