?

Log in

No account? Create an account
The limits of my language mean the limits of my world
 
[Most Recent Entries] [Calendar View] [Friends View]

Saturday, June 28th, 2014

Time Event
10:07a
Придумал неожиданно NP-полную задачу
Disclaimer: задача представляет чисто теоретический / развлекательный интерес. Не для интервью.

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

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

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

<< Previous Day 2014/06/28
[Calendar]
Next Day >>
Guitar Delicacies   About LiveJournal.com