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

Стал интересоваться вопросом равенства 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!), что больше предполагаемого числа атомов во вселенной.

Ответить