29-10-2003 19:44 Задача о скидывании
Некоторое заранее неизвестное количество людей хотят сброситься и купить некий товар. Требуется: придумать схему сбора денег, при которй минимизируется (а) время до покупки, (б) дальнейшая беготня и разборки, кто кому чего должен.
Если бы N было заранее известно, все бы скинулись по 1/N и всё. Для минимизации (а) немного видоизменяем — 1-й сразу покупает вещь, а потом остальные N-1 отдают ему по 1/N.
Но фишка в том, что N заранее неизвестно, а может быть, и не ограничено. Но желающие скидываться могут кончиться в любой момент.
Пример плохого решения:
1-й покупает вещь.
2-й отдаёт ему половину стоимости.
3-й отдаёт 1-му и 2-му по 1/6.
4-й отдаёт 1-му, 2-му и 3-му по 1/12.
…
N-й отдаёт (1..N-1)-му по 1/(N*(N-1)).
Преимущество: после каждой итерации распределение вкладов «справедливое».
Недостаток: требует sum(i-1, i=1..N) ~ O(N^2) передач.
[edit]
Если не требовать, чтобы скидывались строго по одинаковой сумме, то можно придумать схему с N-1 передачей, для которой отклонение от «справедливого» распределения будет вести себя вот так: 
Если бы N было заранее известно, все бы скинулись по 1/N и всё. Для минимизации (а) немного видоизменяем — 1-й сразу покупает вещь, а потом остальные N-1 отдают ему по 1/N.
Но фишка в том, что N заранее неизвестно, а может быть, и не ограничено. Но желающие скидываться могут кончиться в любой момент.
Пример плохого решения:
1-й покупает вещь.
2-й отдаёт ему половину стоимости.
3-й отдаёт 1-му и 2-му по 1/6.
4-й отдаёт 1-му, 2-му и 3-му по 1/12.
…
N-й отдаёт (1..N-1)-му по 1/(N*(N-1)).
Преимущество: после каждой итерации распределение вкладов «справедливое».
Недостаток: требует sum(i-1, i=1..N) ~ O(N^2) передач.
[edit]
Если не требовать, чтобы скидывались строго по одинаковой сумме, то можно придумать схему с N-1 передачей, для которой отклонение от «справедливого» распределения будет вести себя вот так:
Комментарии:
Xirax
29-10-2003 21:25
Дневник • Профиль
Камрад
1-й покупает вещь
Объявляется время, за которое желающие присоединиться должны присоединиться, например, неделя.
В конце недели все пожелавшие собираются и делят деньги.
Преимущество: беготни нет
Недостаток: опоздавшие в пролете
Объявляется время, за которое желающие присоединиться должны присоединиться, например, неделя.
В конце недели все пожелавшие собираются и делят деньги.
Преимущество: беготни нет
Недостаток: опоздавшие в пролете
История интересная, но дико оффтопичная :)
Что касается предложенного решения, то оно предполагает, что N человек можно собрать одновременно, а вероятность этого убывает обратно экспоненциально от N.
Что касается предложенного решения, то оно предполагает, что N человек можно собрать одновременно, а вероятность этого убывает обратно экспоненциально от N.
Камрад
Centaur
Можно и не собираться, 2...N по окончании недели забегают к первому и отдают ему сколько должны N-1 забегов...
С опоздавшими придеться по первому варианту.
Можно и не собираться, 2...N по окончании недели забегают к первому и отдают ему сколько должны
N-1 забегов...С опоздавшими придеться по первому варианту.
На самом деле у меня сложилось впечатление, что, если не требовать, чтобы распределение расходов было абсолютно справедливым, то всё делается за N-1 передачу для произвольного N, а «максимальная несправедливость» мажорируется функцией, обратно пропорциональной N.
Первый чувак покупает вещь (передач — 0, ошибка — 0).
Второй чувак отдаёт первому 1/2 (передач — 1, ошибка — 0).
Третий чувак отдаёт второму 1/4 (передач — 2, ошибка — +1/6 для первого, -1/12 для второго и третьего).
Четвёртый чувак отдаёт первому 1/4 (передач — 3, ошибка — 0).
N-й чувак отдаёт 1+2^ceil(log2(N))-N-му 1/2^ceil(log2(N)) (передач — N-1).
Максимальная ошибка — для первого чувака: он сдал в общей сложности 1/2^floor(log2(N)) вместо 1/N. При постоянном floor(log2(N)) максимум разности будет для N = 2^k - 1, k целое, и он ведёт себя как 1/2^k.
По абсолютной же величине ошибка не превышает 1/6 (когда сбросились трое).
Первый чувак покупает вещь (передач — 0, ошибка — 0).
Второй чувак отдаёт первому 1/2 (передач — 1, ошибка — 0).
Третий чувак отдаёт второму 1/4 (передач — 2, ошибка — +1/6 для первого, -1/12 для второго и третьего).
Четвёртый чувак отдаёт первому 1/4 (передач — 3, ошибка — 0).
N-й чувак отдаёт 1+2^ceil(log2(N))-N-му 1/2^ceil(log2(N)) (передач — N-1).
Максимальная ошибка — для первого чувака: он сдал в общей сложности 1/2^floor(log2(N)) вместо 1/N. При постоянном floor(log2(N)) максимум разности будет для N = 2^k - 1, k целое, и он ведёт себя как 1/2^k.
По абсолютной же величине ошибка не превышает 1/6 (когда сбросились трое).