Разбойники не поделили добычу и умерли)

Dredd · Сообщение **Dredd** » 28 окт 2014, 15:27

Текст под спойлером удобно прятать при обсуждении кино, например. Те, кто фильм смотрел, могут обсуждать под спойлером некоторые сюжетные моменты, которые не хотелось бы раскрывать тем, кто фильм еще не смотрел- чтобы не портить будущий просмотр.

Ian · Сообщение **Ian** » 28 окт 2014, 16:04

цитата:для чего нужно прятать текст под спойлером
Эта традиция пощения первых решений олимпиадных задач четко соблюдается на artofproblemsolving.com, человек придумает свое решение потом откроет спойлер и сравнит. Если сильно отличается, тоже запостит для коллекции. Но не будем переносить оттуда автоматом все традиции. Разница есть. Процент постов, содержащих верные безупречные решения, там 80%, здесь 1-2% (

Ian · Сообщение **Ian** » 28 окт 2014, 17:57

Признаю справедливость нареканий по неточности формулировки задачи. Предложу две равносильных математических модели того, что я имел в виду. В посте 19 это я погорячился,что ни один из разбойников не знает оценки каждой песчинки другими. В предложенных алгоритмах - не знает, но вообще имеет возможность спросить. Таким образом, 1-я модель) даны N песчинок и оценки их $\{a_i\}_{i=1}^N,\;\{b_i\}_{i=1}^N;\;\{c_i\}_{i=1}^N;\;\sum_{i=1}^Na_i=\sum_{i=1}^Nb_i=\sum_{i=1}^Nc_i=1$ (условие нормировки: вся добыча принята за 1) и $\max\{a_i\}<\frac{D}{N},\;\max\{b_i\}<\frac{D}{N};\;\max\{c_i\}<\frac{D}{N}$ (условие бесконечной делимости). Алгоритм раздела множества индексов песчинок на три части А,В,С считается годным, если отличия от максимума стремятся к 0: $\bar{\lim_{N\to\infty}}\max_{a_i,b_i,c_i}\left [\max\{\sum_{i\in B}a_i,\;\sum_{i\in C}a_i \}-\sum_{i\in A}a_i\right ]\geqslant 0$ , и аналогично для В и С.Под спойлером алгоритм годный, внешние максимумы не превосходят D/N.
2-я модель непрерывная: на [0,1] заданы три непрерывные монотонные функции распределения F(x),G(x),H(x), F(0)=G(0)=H(0)=0,F(1)=G(1)=H(1)=1, выражающие оценки А,В,и С соответственно ценности отрезка [0;x], тогда нужно выделить три множества А,В,С, каждое состоит из конечного числа отрезков, никакие отрезки не пересекаются более чем по 1 точке.Объединение АUВUС=[0;1], и совокупное изменение F(x) на множестве А не меньше, чем на В или на С, про G(x) и H(x) аналогично. Алгоритм под спойлером, переведенный на этот язык, приводит к множествам А,В,С , состоящим каждое из 1-2 отрезков

Таланов

Будем делить поровну или по справедливости?
Один из разбойников делит кучу золотого песка на три равные на его взгляд кучи, следовательно его устраивает любая их 3-х. Следующий разбойник выбирает одну из трёх кучек и делит её на его взгляд ровно пополам, следовательно его устраивает любая из 2-х. Оставшийся разбойник из этих половинок выбирает одну себе, вторая достаётся делившему. Далее он делит одну из оставшихся двух кучек попалам, а другой забирает понравившуюся ему половину. У каждого по 1/3 и оставшая кучка достаётся первому делившему. Как тут можно быть кому-то недовольным?

ARRY · Сообщение **ARRY** » 28 окт 2014, 22:26

Таланов писал(а):Source of the post Как тут можно быть кому-то недовольным?

Недоволен может быть только первый деливший. По его критерию все три кучи равны. но в следующих двух дележах он участия не принимал, они проводились по критериям двух других, и у первого есть все основания заподозрить их в несправедливом дележе (по его критерию - это важно) и начать завидовать кому-то из них.

Таланов

ARRY писал(а):Source of the post Недоволен может быть только первый деливший.

Хорошо, пойдем дальше. Теперь когда на руках у разбойников по кучке золота сделаем перераспределение собственности по предложенной схеме. Каждый делит свою кучку на 3, остальные двое учавствуют в дележе. Здесь уже полнейшая симметрия.

ARRY · Сообщение **ARRY** » 29 окт 2014, 00:53

Тоже не получается до конца. Делить то он свою кучку делит, да вот остальные двое пальчиком тычут в олну и ту же кучку, и ничего не остаётся как применить один из алгоритмов Ianа.

Таланов

Вы не разобрались в моей схеме.

Ian · Сообщение **Ian** » 29 окт 2014, 06:07

ARRY писал(а):Source of the post один из алгоритмов Ianа.

Не подставляйте меня,алгоритм Брамса и Тейлора, задача о разделе торта, я только переводчик их путаного, надо признаться, текста.Но они его непрерывно совершенствуют в следующих работах.

ARRY · Сообщение **ARRY** » 29 окт 2014, 07:36

Ian писал(а):Source of the post $\max\{a_i\}<\frac{D}{N},\;\max\{b_i\}<\frac{D}{N};\;\max\{c_i\}<\frac{D}{N}$

Наверное, точнее везде нестрогое неравенство, нет?

Ian писал(а):Source of the post $$Ñ\bar{\lim_{N\to\infty}}\max_{a_i,b_i,c_i}\left [\max\{\sum_{i\in B}a_i,\;\sum_{i\in C}a_i \}-\sum_{i\in A}a_i\right ]\geqslant 0$$

Наверное, имелось в виду:
$\bar{\lim_{N\to\infty}}\max_{a_i,b_i,c_i}\left [\max\{\sum_{i\in B}a_i,\;\sum_{i\in C}a_i \}-\sum_{i\in A}a_i\right ]= 0$
Нет?
А вообще-то непрерывная модель более понятна, даже на интуитивном уровне.

yourdomain.com