Eugene Kirpichov (antilamer) wrote,
Eugene Kirpichov
antilamer

Придумал неожиданно NP-полную задачу

Disclaimer: задача представляет чисто теоретический / развлекательный интерес. Не для интервью.

Вы организуете событие, на котором N мест. Люди могут покупать билеты, в т.ч. билеты на несколько мест сразу (например, я могу купить билет на 4 человека).
Допускается продажа бОльшего числа мест, чем есть. Тогда после окончания продажи билетов проводится лотерея и те, чьи билеты не "выиграли", получают деньги назад.
Нужно провести справедливую лотерею:
1) Билет на несколько мест атомарен - он либо "выигрывает" целиком, либо "проигрывает" целиком.
2) Для каждого человека, который хотел пойти, вероятность пойти должна быть одинаковой.
3) Эта вероятность должна быть максимальна (иначе можно было бы просто вернуть всем деньги).

Пример: 8 мест; хотят пойти 12 человек: куплены билеты на 3, 4, 5.
Одно из оптимальных решений такое: бросить монетку, и либо выбрать {3, 4}, либо {5}.
Тогда у всех 12 человек вероятность пойти 1/2.

Заметьте, что {5} не максимально - можно было бы добавить и {3}, но тогда нарушилось бы условие справедливости - у этих троих вероятность была бы 1, а у четверых и пятерых - 1/2.
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 24 comments