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

158
1
7
22 апреля
17:40
апрель
2016

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

2
6
Если вы знаете ответ на этот вопрос и можете аргументированно его обосновать, не стесняйтесь высказаться
Ответить самому
Выбрать эксперта