не, я серьезно. на эти 8 мест покупают 4 человека по два билета. и 8 человек по 6 билетов. почему варианты 2+6 справедливы, а вариант 2+2+2+2 справедливость нарушает?
Справедливость относится не к варианту, а к схеме выбора варианта. Если согласно схеме вероятность у всех получается одинаковая - значит, схема справедлива. Если разная - значит, несправедлива.
Например, в случае 3,4,5 / 8, схема "выбрать с равной вероятностью либо {3,4}, либо {3,5}" несправедлива, т.к. эти трое попадут в любом случае (у меня в посте тупая ошибка, я написал 2/3, а на самом деле просто 1), а четверо и пятеро - только в каждом втором.
Если на 8 мест покупают 4 человека по 2 (покупатели 2a..2d) и 8 по 6 (покупатели 6a..6h), то оптимальное решение, подозреваю, такое (не уверен точно, т.к. задача, повторюсь, NP-полная, а программу для ее решения я быстро написать не могу) - выбрать с равной вероятностью один из следующих вариантов: {2a,6a}, {2b,6b}, {2c,6c}, {2d,6d}, {6e}, {6f}, {6g}, {6h}.
Тогда получается, что у каждого из 56 желающих пойти вероятность выиграть - 1/8. Это хуже, чем 1/7, если бы билеты были не атомарны, но несправедливости я тут не вижу - вероятность у всех одинаковая.
А почему эта задача вообще в NP? Что использовать в качестве сертификата? Схему проведения с вероятностями? Но так как в схеме вохможны повторы, то я не понимаю, почему она будет полиномиального размера?
Эту задачу можно переформулировать так: У нас есть множество X, например X = {3, 4, 5}. Найти семейство S комбинаций из элементов X, такое, что вес каждой комбинации <= N, и для каждого элемента x \in X, в S одинаковое количество комбинаций, включающих x (назовём это количество R - "число реплик"). Например, S = {{3,4}, {5}}. Или, если X = {1a,1b,1c}, то S = {{1a, 1b}, {1b, 1c}, {1a, 1c}}. Для такого S, получается схема - выбрать случайный элемент S, а вероятность успеха у каждого участника R / |S|.
Нужно максимизировать R / |S|, и мой коллега меня вчера убедил, что нет смысла искать R > |X|, но я уже забыл, почему.
Отсюда понятно, что задача в NP (сертификат - S); и мне кажется, что какая-нибудь из задач о рюкзаке сводится к поиску S с R=1.
Comments 22
какой-то пидор-спекулянт купил кучу билетов, а из-за этого должны остальные страдать?
Reply
Reply
на эти 8 мест покупают 4 человека по два билета.
и 8 человек по 6 билетов.
почему варианты 2+6 справедливы, а вариант 2+2+2+2 справедливость нарушает?
Reply
Например, в случае 3,4,5 / 8, схема "выбрать с равной вероятностью либо {3,4}, либо {3,5}" несправедлива, т.к. эти трое попадут в любом случае (у меня в посте тупая ошибка, я написал 2/3, а на самом деле просто 1), а четверо и пятеро - только в каждом втором.
Если на 8 мест покупают 4 человека по 2 (покупатели 2a..2d) и 8 по 6 (покупатели 6a..6h), то оптимальное решение, подозреваю, такое (не уверен точно, т.к. задача, повторюсь, NP-полная, а программу для ее решения я быстро написать не могу) - выбрать с равной вероятностью один из следующих вариантов: {2a,6a}, {2b,6b}, {2c,6c}, {2d,6d}, {6e}, {6f}, {6g}, {6h}.
Тогда получается, что у каждого из 56 желающих пойти вероятность выиграть - 1/8. Это хуже, чем 1/7, если бы билеты были не атомарны, но несправедливости я тут не вижу - вероятность у всех одинаковая.
Reply
Reply
У нас есть множество X, например X = {3, 4, 5}.
Найти семейство S комбинаций из элементов X, такое, что вес каждой комбинации <= N, и для каждого элемента x \in X, в S одинаковое количество комбинаций, включающих x (назовём это количество R - "число реплик"). Например, S = {{3,4}, {5}}. Или, если X = {1a,1b,1c}, то S = {{1a, 1b}, {1b, 1c}, {1a, 1c}}.
Для такого S, получается схема - выбрать случайный элемент S, а вероятность успеха у каждого участника R / |S|.
Нужно максимизировать R / |S|, и мой коллега меня вчера убедил, что нет смысла искать R > |X|, но я уже забыл, почему.
Отсюда понятно, что задача в NP (сертификат - S); и мне кажется, что какая-нибудь из задач о рюкзаке сводится к поиску S с R=1.
Reply
Reply
Reply
(The comment has been removed)
Reply
Reply
Reply
Leave a comment