Разбойники не поделили добычу и умерли)
Разбойники не поделили добычу и умерли)
Текст под спойлером удобно прятать при обсуждении кино, например. Те, кто фильм смотрел, могут обсуждать под спойлером некоторые сюжетные моменты, которые не хотелось бы раскрывать тем, кто фильм еще не смотрел- чтобы не портить будущий просмотр.
Последний раз редактировалось Dredd 27 ноя 2019, 19:22, всего редактировалось 1 раз.
Причина: test
Причина: test
Разбойники не поделили добычу и умерли)
цитата:для чего нужно прятать текст под спойлером
Эта традиция пощения первых решений олимпиадных задач четко соблюдается на artofproblemsolving.com, человек придумает свое решение потом откроет спойлер и сравнит. Если сильно отличается, тоже запостит для коллекции. Но не будем переносить оттуда автоматом все традиции. Разница есть. Процент постов, содержащих верные безупречные решения, там 80%, здесь 1-2% (
Эта традиция пощения первых решений олимпиадных задач четко соблюдается на artofproblemsolving.com, человек придумает свое решение потом откроет спойлер и сравнит. Если сильно отличается, тоже запостит для коллекции. Но не будем переносить оттуда автоматом все традиции. Разница есть. Процент постов, содержащих верные безупречные решения, там 80%, здесь 1-2% (
Последний раз редактировалось Ian 27 ноя 2019, 19:22, всего редактировалось 1 раз.
Причина: test
Причина: test
Разбойники не поделили добычу и умерли)
Признаю справедливость нареканий по неточности формулировки задачи. Предложу две равносильных математических модели того, что я имел в виду. В посте 19 это я погорячился,что ни один из разбойников не знает оценки каждой песчинки другими. В предложенных алгоритмах - не знает, но вообще имеет возможность спросить. Таким образом, 1-я модель) даны N песчинок и оценки их(условие нормировки: вся добыча принята за 1) и (условие бесконечной делимости). Алгоритм раздела множества индексов песчинок на три части А,В,С считается годным, если отличия от максимума стремятся к 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 отрезков
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 отрезков
Последний раз редактировалось Ian 27 ноя 2019, 19:22, всего редактировалось 1 раз.
Причина: test
Причина: test
Разбойники не поделили добычу и умерли)
Будем делить поровну или по справедливости?
Один из разбойников делит кучу золотого песка на три равные на его взгляд кучи, следовательно его устраивает любая их 3-х. Следующий разбойник выбирает одну из трёх кучек и делит её на его взгляд ровно пополам, следовательно его устраивает любая из 2-х. Оставшийся разбойник из этих половинок выбирает одну себе, вторая достаётся делившему. Далее он делит одну из оставшихся двух кучек попалам, а другой забирает понравившуюся ему половину. У каждого по 1/3 и оставшая кучка достаётся первому делившему. Как тут можно быть кому-то недовольным?
Один из разбойников делит кучу золотого песка на три равные на его взгляд кучи, следовательно его устраивает любая их 3-х. Следующий разбойник выбирает одну из трёх кучек и делит её на его взгляд ровно пополам, следовательно его устраивает любая из 2-х. Оставшийся разбойник из этих половинок выбирает одну себе, вторая достаётся делившему. Далее он делит одну из оставшихся двух кучек попалам, а другой забирает понравившуюся ему половину. У каждого по 1/3 и оставшая кучка достаётся первому делившему. Как тут можно быть кому-то недовольным?
Последний раз редактировалось Таланов 27 ноя 2019, 19:22, всего редактировалось 1 раз.
Причина: test
Причина: test
Разбойники не поделили добычу и умерли)
Недоволен может быть только первый деливший. По его критерию все три кучи равны. но в следующих двух дележах он участия не принимал, они проводились по критериям двух других, и у первого есть все основания заподозрить их в несправедливом дележе (по его критерию - это важно) и начать завидовать кому-то из них.Таланов писал(а):Source of the post Как тут можно быть кому-то недовольным?
Последний раз редактировалось ARRY 27 ноя 2019, 19:22, всего редактировалось 1 раз.
Причина: test
Причина: test
Разбойники не поделили добычу и умерли)
Хорошо, пойдем дальше. Теперь когда на руках у разбойников по кучке золота сделаем перераспределение собственности по предложенной схеме. Каждый делит свою кучку на 3, остальные двое учавствуют в дележе. Здесь уже полнейшая симметрия.ARRY писал(а):Source of the post Недоволен может быть только первый деливший.
Последний раз редактировалось Таланов 27 ноя 2019, 19:22, всего редактировалось 1 раз.
Причина: test
Причина: test
Разбойники не поделили добычу и умерли)
Тоже не получается до конца. Делить то он свою кучку делит, да вот остальные двое пальчиком тычут в олну и ту же кучку, и ничего не остаётся как применить один из алгоритмов Ianа.
Последний раз редактировалось ARRY 27 ноя 2019, 19:22, всего редактировалось 1 раз.
Причина: test
Причина: test
Разбойники не поделили добычу и умерли)
Вы не разобрались в моей схеме.
Последний раз редактировалось Таланов 27 ноя 2019, 19:22, всего редактировалось 1 раз.
Причина: test
Причина: test
Разбойники не поделили добычу и умерли)
Не подставляйте меня,алгоритм Брамса и Тейлора, задача о разделе торта, я только переводчик их путаного, надо признаться, текста.Но они его непрерывно совершенствуют в следующих работах.
Последний раз редактировалось Ian 27 ноя 2019, 19:22, всего редактировалось 1 раз.
Причина: test
Причина: test
Разбойники не поделили добычу и умерли)
Наверное, точнее везде нестрогое неравенство, нет?Ian писал(а):Source of the post
Наверное, имелось в виду: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$$
Нет?
А вообще-то непрерывная модель более понятна, даже на интуитивном уровне.
Последний раз редактировалось ARRY 27 ноя 2019, 19:22, всего редактировалось 1 раз.
Причина: test
Причина: test
Вернуться в «Олимпиадные задачи»
Кто сейчас на форуме
Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 0 гостей