Здравствуйте, WeCom, Вы писали:
WC>Здравствуйте, BUran, Вы писали:
WC>>>А насчет сговора, обьясните мне кто-нибудь чем можно соблазнить пассажиров с номерами от 50 до 100 голосовать за какую-нибудь остановку до 50-й. А если они не будут голосовать, то и остановки не будет, потому что их большинство. BU>>Тем например, что 60 знает, что если сделают остановку на 30-й, то будет остановка и на 60-й, и не придется выходить на 50-й или 75-й, например.
WC>Это догадки ничем не подкрепленные и на мой взгляд неверные! Неверные по следующей причине. Предположим 60-й решает голосовать за 30-ю остановку и его голос оказывается решающим на 30-й остановке... В общем я уже писал выше похожие рассуждения. 60-му будет выгоднее голосовать за 31-ю остановку, чем за 30-ю, потому что он ничего от этого не теряет!!!
Тем более ничем не подкреплено. По-моему, как раз он теряет в этом случае возможность выйти на 60 остановке. (Цифры 30 и 60, понятно, взяты с потолка) >Но если его голос будет решающим на 31-й, то ему выгоднее голосовать на 32-й, и т.д..... А если его голос где-то не решающий, то ему нафиг не надо голосовать В итоге получается что голосовать они все будут начиная со своей остановки. А вот выходить?...
BU>>А что ты ответишь про то, чтобы подумать о том, чтобы выйти заранее, до своей остановки?? WC>Думаю имеет смысл разделить задачу на две. С разрешением этого и без.
Здравствуйте, Octane, Вы писали:
O>Здравствуйте, WeCom, Вы писали:
WC>>Нет нельзя забывать! Утверждаешь что именно я это забыл? Тогда обьясни мне зачем кому-то кроме номера1 голосовать за первую остановку? Они ведь могут проголосовать все вместе за вторую остановку, не так ли? И тогда для всех них после второй остановки ситуация будет точно такая же как если бы они голосовали и за первую и за вторую остановку. Но доедут они до дома 100% быстрее если не будут голосовать за первую остановку. Поэтому они за первую остановку точно голосовать не станут. Уже это говорит о том, что твой ответ не верен. Вот если бы первый мог устраивать подлости (ехать до 100-й остановки), тогда было бы наверное по-другому.
O>До дома большинство быстрее доедет(даже если перед этим будут лишние остановки),чем дойдет(преодолев пешком k остановок пути)
И что ты этим сказал? Я же просил, и еще раз прошу, обьясни мне зачем кому-то кроме номера1 голосовать за первую остановку? Не общими словами, а конкретно. Покажи мне в частности, чем будет отличатся ситуация после второй остановки для пассажиров с номерами от второго до сотого в случае когда они голосуют и за первую и за вторую остановку от случая когда они голосуют только за первую остановку!!! Я утверждаю, что ничем — первый и второй уже вышли в обоих случаях, а все остальные внутри автобуса. Из того что для них ситуация ничем не отличается, я делаю вывод, что за первую остановку 99 человек голосовать не бу-дут. Неужели все еще непонятно?
A>>А вообще задача некорректна тем что не известно сколько времени экономит автобус на проезде остановки, и на сколько больше времени тратит пассажир если вышел не на своей.
WC>Это имхо лишнее. Достточно сказать, что каждый пассажир руководствуется единственным желанием — выйти как можно ближе к своей остановке.
Совсем не лишнее. Возьмем несколько ярких случаев которые могут сильно изменить решение задачи
# скорость автобуса значительно ниже скорости пассажиров
— все выйдут на первой же)
# 99 остановок находятся на растоянии друг от друга в 1 сек пути пешком, зато некая другая от стоит от других в 1 неделю — это оч. сильно поменяет расклад желающих выходить на этой остановке =)
# растояния одинаковые, время которое экономит автобус при проезде остановки 1 мин, от одной остановки до другой пешком 10 недель и люди настолько умные что не только могут строить прогнозы но и разговаривать и договариваются чтобы никому западло не делать поскольку в западло может попасть почти каждый если вдруг договор будет нарушатся.
#автобус движется не по прямой (а кто вам сказал и где вы видели такие маршруты?) соотсвеннно есть такая ситуевина от 100 до 98 идти гораздо меньше чем от 99 до 98 — тогда умный 99 будет голосовать чтобы 98 вышел на своей, а не проголосовал против его выхода на 99.
SS>>>1 все пассажиры тупы и не делают прогнозы
A>>Автобус проедет маршрут без остановок.
WC>Т.е. настолько тупы, что даже проехав свою остановку не желают выходить?
SS>>>2 все пассажиры умны и делают прогнозы о том как им лучше голосовать
A>>Автобус проедет маршрут со всеми остановками.
WC>Ну как минимум на номере 98, автобус не остановится! Имеем 3 человека — 98,99 и 100 и автобус подьезжает к 98-й остановке. Скажите, какой смысл номерам 99 и 100 голосовать за остановку на 98-й? Об альтруизме в задаче разговора кажется не было.
ээээ, я же улыбку там поставил — все подобные умозаключения могут быть как справедливыми так и не справедливыми в зависимости от разных дополнительных условий .
Здравствуйте, Apostate, Вы писали:
A>>>А вообще задача некорректна тем что не известно сколько времени экономит автобус на проезде остановки, и на сколько больше времени тратит пассажир если вышел не на своей.
WC>>Это имхо лишнее. Достточно сказать, что каждый пассажир руководствуется единственным желанием — выйти как можно ближе к своей остановке.
A>Совсем не лишнее. Возьмем несколько ярких случаев которые могут сильно изменить решение задачи
Можно совет?
Когда приходят такие мысли в голову, сделай вот как. Попробуй так проинтерпретировать непонятные вещи, чтобы задача имела однозначное решение. Если такого не получается, то из всех мыслимых тобой непротиворечивых дополнений выбери такие при которых задача будет наиболее интересной и конечно же без абсурдных с точки зрения физики и здравого смысла условий. Реши эту задачу. И предложи ответ с указанием, какие дополнения ты принял в задаче. Если ты ошибешься и в оригинальном условии другое, а автор пропустил, не волнуйся, в любом случае найдутся люди, которые оценят твой ответ по-достоинству.
А то как то на мой взгяд несерьезно получается, 1 сек пути, автобус медленнее пассажира...
Непонятна фраза "сходит на ближайшей к нужной"? — Уверен следует считать расстояние между остановками, как разность номеров.
Задумываешься о возможности сговора? — Прочитай внимательно принятое автором уточнение "каждый пассажир руководствуется единственным желанием — выйти как можно ближе к своей остановке". Собственно ради этого одного выделенного слова я и просил автора уточнить.
Для Octane:
ошибочка:
WC>... в случае когда они голосуют и за первую и за вторую остановку от случая когда они голосуют только за вторую остановку!!!...
Может изменить формулировку так: если чел проголосовал, остановились — то он и выходит?
А иначе, чем плох вариант, что голосовать всегда "за"? И ограничений на количество остановок нет...
Тогда задача сразу становится содержательной.
ИМХО, надо попробовать решить задачу с конца.
Леммы.
1) выходят по порядку.
док-во очевидно.
2) выходит некоторый "отрезок" чуваков То есть с какого-то до какого-то.
следствие 1.
3) Среди вариантов есть вариант, при котором каждый раз голосует больше половины, причем голосующие как раз при удачном голосовании выходят.
вариантов — конечное число. Есть вариант, например, вылезти всем на первой остановке. Такой вариант неоптимальный => есть посл-сть более оптимальных вариантов. (А иначе — он — оптимальный ) => есть самый оптимальный.
4) Среди таких "наименьших" есть наименьший по цифрам. Например, 0101010...01 -неоптимален, т.к. оптимальнее 0101....10 —
(здесь 0 и 1 — делать i-ю остановку или нет)
Вот его-то и будем искать.
---
1) последняя остановка — 100.
на ней вышло 0 — возможно, если все вышли раньше.
на ней вышел 1 — возможно, это 100-ый.
на ней вышло 2 — невозможно, можно было бы выйти и на 99-ой. (ищем минимальный вариант из наилучших)
на ней вышло 3 и более — невозможно, так как большинство вышло бы раньше.
2) последняя остановка — 99
на ней вышло 0 — невозможно (нафига тогда останавливаться?)
вышло 1 — последний? невозможно. доедет до 100.
вышло 2 — запросто.
вышло 3 — вряд ли. Последний доедет в одиночку до своей.
Брр, неправильно обозначил. Начнем снова, только указывать, сколько осталось, и сколько выйдет:
1) 100-ая. осталось:
0: выйдет 0
1: выйдет 1
2: невозможно (выйдут раньше в силу леммы 4)
...
2) 99-ая
0: выйдет 0
1: выйдет 0
2: выйдет 2 (будем считать, что голосовало большинство, т.е. 2)
3: выйдет 2
4: выйдет 3
5: выйдет 4 (впрочем, опять же невозможно)
...
3) 98-я
0: 0
1: 0
2: 0
3: 2 (вариант 0 не проходит по л.4)
4: 3 (есть 4:0 и 4:4 — они хуже)
5: 3
6: 4
...
4) 97-я
0: 0
1: 0
2: 0
3: 0
...
Блин, сложно, долго, нудно... надо программу писать...
Правила следующие: для каждой остановки и каждого количества смотрим: если не 0 — то это большинство, которое реально выходит. Если не выходим щас — смотрим, когда сможем выйти. Это мы знаем. Можем соптимизировать значит. Вот.
WC>Можно совет? WC>Когда приходят такие мысли в голову, сделай вот как. Попробуй так проинтерпретировать непонятные вещи, чтобы задача имела однозначное решение. Если такого не получается, то из всех мыслимых тобой непротиворечивых дополнений выбери такие при которых задача будет наиболее интересной и конечно же без абсурдных с точки зрения физики и здравого смысла условий. Реши эту задачу. И предложи ответ с указанием, какие дополнения ты принял в задаче. Если ты ошибешься и в оригинальном условии другое, а автор пропустил, не волнуйся, в любом случае найдутся люди, которые оценят твой ответ по-достоинству.
=), спасибо за совет, он хороший, но мне кажется он немного не к месту и вот почему
WC>Задумываешься о возможности сговора? — Прочитай внимательно принятое автором уточнение "каждый пассажир руководствуется единственным желанием — выйти как можно ближе к своей остановке". Собственно ради этого одного выделенного слова я и просил автора уточнить.
при таком условии ответ очевиден — автобус остановится на всех остановках, есть желание выйти самому на своей, нет никакого желания мешать другим выйти на их остановке. Здесь и не пахнет альтруизмом, достаточно элементарной рефлексии что пассажиры тоже люди как я, и они тоже хотят выйти на своей. Если настолько туп, что рефлексии нет — автобус проедет без остановок. Этот ответ я и дал в самом начале.
Вот, но чтобы найти здравую идею в задаче, я предположил что пассажиры руководствуются другой, более естевенной целью — как можно раньше прибыть к месту своего назначения, при этом известно сколько времени экономит автобус на проезде остановки, и на сколько больше времени тратит пассажир если вышел не на своей, хотя впрочем можно обойтись соотношением.
Правда если руководствоваться совсем здравым смыслом, надо еще знать отношение скоростей пассажира пешком и на автобусе, поправочные коээфициенты для путешествия от одной остановки до другой пешком и автобусом (разные маршруты и скорости на местности) и т.д. но это уже согласен больше из области более комплесного решения, но как ответ на то что условий больше ну никаких в принципе не надо — самое то.
A>Если настолько туп, что рефлексии нет — автобус проедет без остановок.
Хотя насчет тупизны спорно тем что в природе существует бесконечное разнообразие тупизны и только одна едиственная разумность.
Вообщем возможны варианты тупости/незнания.
Не знает что в автобусе другие люди. Не знает что для каждой остановки есть люди которые хотят на ней выйти. Не знает что он тоже люди. Не знает что автобус едет от 1 остановки до 100 последовательно, и если проехал свою остановку то дальше он будет только удалятся. Не знает какая сейчас остановка. Не знает что он может проехать свою остановку до тех пор, пока он ее не проедет. Не знает что он уже проехал свою остановку. Не знает какая остановка его. Не умеет считать (дети тоже пассажиры, да?). И т.д.
Так вот, тупость о которой идет речь. Допустим его остановка N и у него единственное желание выйти как можно ближе к этой остановке, голосования —
1 нет бывает и ближе,
...
N-1 нет бывает и ближе
N да, ближе не бывает
N+1 нет, бывает и ближе
...
100 нет, бывает и ближе
Если он туп но умеет делать прогнозы относительно движения автобуса но не знает о голосовании другими
1 нет бывает и ближе. И еще будет.
...
N-1 нет бывает ближе. И еще будет.
N да, ближе не бывает
N+1 да, бывает и ближе. Но уже не будет.
N+2 да, бывает и ближе. Но уже не будет.
...
до тех пор пока не выйдет
То решение (при равенстве голосов остановка) 50, 75, 88, 94, 97, 99,100
соотвественнои вышло на этой остановке 50, 25, 13, 6, 3,2,1
и на момент да-голосования в автобусе было 100,50 ,25, 12,6,3,1
Если они тупы но умеют делать прогнозы относительно движения автобуса и очень простенькие прогнозы по поводу голосования( могут проголосовать против), но при этом нет понимания что он сейчас голосует не только для себя и выходить ему не обязательно, и при этом полный оптимист
1 нет бывает и ближе. И еще будет. И голосование будет положительным.
...
N-1 нет бывает ближе. И еще будет. И голосование будет положительным.
N да, ближе не бывает
N+1 да, бывает и ближе. Но уже не будет.
N+2 да, бывает и ближе. Но уже не будет.
...
до тех пор пока не выйдет
То решения те же что и выше
50 75 88 94 97 99 100
51 76 89 95 98 100
Тоже но если они полные пессимисты
1. нет бывает и ближе. И еще будет. Но голосование во всех случаях будет отрицательным.
— все выйдут на первой же
и т.д. и т.п.
И только один умный вариант
1. да, а зачем парится и голосовать против?
...
до тех пор пока не выйдет
Ситауция аналогичная как при голосовании скажем всей страны. Разве ваш один голос что-то решает? Но если вы проголосуете так как считаете нужным — есть шанс что также поступят остальные.
В данном случае всем выгодно всегда голосовать "за".
Прямо золотое правило морали — "относись к другим так, как хочешь что-бы относились к тебе".
Здравствуйте, IO, Вы писали:
IO>В данном случае всем выгодно всегда голосовать "за".
Учитывая, что по условию задачи, "все руководствуются единственным желанием..." зачем номеру100 голосовать за какую-нибудь остановку кроме его личной?
---
100 остановок — это конечно много. Сложно уловить все возможные комбинации...
Если посмотреть на ту же задачу с пятью остановками-пассажирами, то вот, что интересное получается. Полагаем, для того чтобы автобус остановился нужно строгое большинство голосов. Номер пятый собирается голосовать "за" только на пятой остановке. Номер первый — на всех. Номер второй — начиная со второй (или даже с первой — неважно) остановки. — Это для них оптимальные варианты поведения.
Так вот, если четвертый проголосует за вторую остановку, то он сделает доброе дело для первого и второго, подлянку в отношении третьего и обеспечит себе выход на своей остановке (вместе с третим). Если же он за вторую голосовать не будет, то на третей остановке выйдут 1-3, а он (четвертый) вместе с пятым поедет до конечной.
Получается, что то решение, которое я проталкивал, будет верным только с дополнительной оговоркой, что выходят все голосовавшие "за".
Здравствуйте, WeCom, Вы писали:
WC>Учитывая, что по условию задачи, "все руководствуются единственным желанием..." зачем номеру100 голосовать за какую-нибудь остановку кроме его личной?
Это вообще то очень неочевидно, но мне кажется логика тут есть.
Поставлю вопрос прямо: если я буду голосовать всегда "за", как изменится вероятность того, что все остальные тоже всегда будут голосовать "за"?
Мне кажется, что возрастет.
Здравствуйте, IO, Вы писали:
IO>Поставлю вопрос прямо: если я буду голосовать всегда "за", как изменится вероятность того, что все остальные тоже всегда будут голосовать "за"? IO>Мне кажется, что возрастет.
В условии задачи об этом не говорится! Нооборот, неявно указывается, что каждый сам за себя. Т.е. как минимум нельзя расчитывать на то, что своими голосами "за" удасться пробудить совесть. И более того, учитывать, что голосуя "за" можно и навредить себе. Например, 3 остановки — 3 пассажира. Для остановки надо строгое большинство. Второй решает действовать твоим методом. И... помогает первому сойти на своей остановке. А вот третий — он асоциальный элемент и его устроят 30 сэкономленых на второй остановке секунд и поэтому он не даст второму сойти на своей остановке. Хотя второй мог бы при желании (а оно по условию у него должно было бы быть) обеспечить себе выход на своей остановке.
Здравствуйте, WeCom, Вы писали:
WC>Здравствуйте, SanSoft, Вы писали:
SS>>Решение принимается простым большинством голосов.
WC>Если при равенстве голосов остановка отсутствует, и выходить раньше своей остановки нельзя, то тогда ответ на задачу в обоих случаях — 51,77,89,95,98,100.
по моему все таки таки
51 76 89 95 98 100
76 потому что их было 49 в автобусе и 25 из них захотели выйти
89 потому что их было 24 в автобусе и 13 из них захотели выйти
Здравствуйте, Apostate, Вы писали:
SS>>>Решение принимается простым большинством голосов.
WC>>Если при равенстве голосов остановка отсутствует, и выходить раньше своей остановки нельзя, то тогда ответ на задачу в обоих случаях — 51,77,89,95,98,100.
A>по моему все таки таки A>51 76 89 95 98 100
A>76 потому что их было 49 в автобусе и 25 из них захотели выйти A>89 потому что их было 24 в автобусе и 13 из них захотели выйти
A>остальное аналогично
Здравствуйте, WeCom, Вы писали:
SS>>1 все пассажиры тупы и не делают прогнозы WC>Тогда они очевидно будут голосовать "против" до остановки со своим номером, а далее будут голосовать "за" до тех пор пока автобус не остановится. И тогда все голосовавшие за, сойдут и ситуация повторится, только остановок останется меньше. WC>Если считать, что при равенстве голосов принимается решение "остановиться", то очевидно остановки будут иметь номера 50,75,88,94,97,99,100.
Согласен. При тупом поведении — логика проста => чистая математика.
SS>>>2 все пассажиры умны и делают прогнозы о том как им лучше голосовать
все пассажиры умны — это что, автобус с РСДН-овцами? Мужики — это намек! Пора собирать большую реалку и переть куда-нить на экскурсию с пивом Заодно помучим водилу автобуса
А вообще:
1. Они могут пойти по пути демократии и устроить голосование, через сколько остановок тормозить.
При голосовании о варианте "через 1" поднимут руки все четные пассажиры.
"через 2" — каждый третий.
"через 3" — каждый четвертый.
"через 4" — каждый пятый.
и т.д.
Т.е. имеем: либо на каждой, либо через одну, если таки решат, что на каждой не катит
2. Можно так-же проголосовать, кто из пассажиров на какое максимальное количество остановок от своей согласен выйти.
Тогда, если, скажем, решится, что большинство согласно выйти максимум на соседней со своей остановкой, следует останавливаться на каждой третьей(две подряд пропускаем), если согласны максимум через одну от своей — на каждой пятой(четыре пропускаем), и т.д.
Я лично из этих двух вариантов больше склоняюсь ко второму, как к более разумному.
Поскольку в условиях задачи не чего не говориться про желание посажиров доехать как можно быстрее то им логично голосовать все время за , вседствии чего все выйдут именно на тех остановках где им нужно.
Здравствуйте, Mikhail_T, Вы писали:
M_T>Поскольку в условиях задачи не чего не говориться про желание посажиров доехать как можно быстрее то им логично голосовать все время за , вседствии чего все выйдут именно на тех остановках где им нужно.
Все будет именно так, как ты говоришь. Точнее, почти так...
Потому что на полпути молодого человека под номером сто только что сдавшего сессию , невыспавшегося и к тому же отметившего успешную сдачу с друзьями слегка разморит в душном автобусе и он заснет (ему-то бояться нечего, он свою остановку не пропустит). В итоге проспит он все остановки вплоть до своей конечной, на которой его и растолкают водитель да бабушка под номером девяносто девять , которая не спала и честно голосовала на всех остановках "за" (хотя спрашивается зачем она за 98 голосовала, но это уже не важно).
И будет той бабушке так обидно , что не ее остановку пропустили, что она мало того, что молодому человеку выскажет все, что о нем думает, так она еще и к диспетчеру зайдет и на водителя так нажалуется , что тот дабы сберечь свои нервы и место работы должен будет взять свой личный автотранспорт и довезти бабушку прямо до дома рядом с 98-й остановкой.
Мораль сей басни такова. Коли возишь людей, так вози людей, а не загадывай ребусов! Тем более, что все равно себе выйдет дороже.
Здравствуйте, WeCom, Вы писали:
WC>но я просто фигею, как народу хочется превратить задачку из математической, в задачку по социальной психологии.
Математически ИМХО слишком нечеткое условие, понимание задачи плавает.
Единственное четкое, что здесь можно выделить, это вариант 1, предложенный тобой(с рядом чисел, когда "все тупые").
Но автор темы хочет чего-то еще, задавая вопрос "когда все умные".... а вот чего, не понятно...
В итоге получается что голосовать они все будут начиная со своей остановки. А вот выходить?...
) => есть самый оптимальный.
, невыспавшегося 
и к тому же отметившего успешную сдачу с друзьями 
, что тот дабы сберечь свои нервы и место работы должен будет взять свой личный автотранспорт и довезти бабушку прямо до дома рядом с 98-й остановкой. 