?

Log in

No account? Create an account

Entries by category: криминал

Category was added automatically. Read all entries about "криминал".

Решил репостнуть комментарий к себе в журнал. Помните, у меня был коротенький цикл "критический анализ", и про мое отношение и идеократии тоже было. Так вот, эта инфографика является хорошей иллюстрацией высказывания "есть ложь, наглая ложь и статистика".Read more...Collapse )

Задача об m мафиози

Вдохновившись "задачей византийских генералов", мы с Ваней стали проверять ее формулировки на прочность. И вспомнили, что есть одна довольно популярная игра, где коммуникации идеальны, а процессоры нет.
Те, кто когда-нибудь играл в "мафию", знают, что чем больше мафиози, тем больше у них шансов на успех и наоборот. Так вот существует ли соотношение, при котором победа мафии уже невозможна математически? Иными словами, у города существует выигрышная стратегия?
Важное уточнение:
1) Используется одна обычная колода карт, не предназначенная специально для этой игры, все используемые карты известны заранее; то есть, ни у кого нет двух неразличимых карт и нет карт, которые в игре, но об этом неизвестно;
2) Нельзя показывать свою карту, в остальном можно говорить что угодно; то есть, доступен обмен любой информацией по надежным коммуникациям, но нет прямых способов проверить полученную информацию на достоверность
3) Никто в принципе не запрещает делать записи; это чисто для облегчения задачи, память у людей не идеальная;
4) Есть только мафия и мирные; это для облегчения задачи нам, о последствиях введения других карт еще поговорим.

Так вот, как ни странно, при таких уточнениях решение существует. При n человек в игре, из которых m - мафиози, выигрышная для города стратегия существует в случае n>4m+1. В случае равенства, существует стратегия, где в конце с вероятностью 50% остаются двое мирных, иначе - мирный и мафия.

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

Последовательность действий для каждого i-го конфликта

Шаг 1. А и Б вступили в i-й по счету конфликт. На суде убиваем А. Считаем, что карты не вскрываются, и мы не можем точно узнать, кем он был.
Шаг 2. Ночью кого-нибудь убили. Если это был Б, переходим к шагу 1 для следующего конфликта.
Шаг 3. Если это был не Б, на суде убиваем Б.
Шаг 4. Ночью мафия убила еще кого-нибудь.

На следующий день, осталось не более m-1 конфликтов, m-1 мафиози и всего не менее 4(m-1)+1 человек в игре. Следует заметить, что эти "не более" и "не мение" можно заменить на "ровно" если мы мафия не убивает людей, вовлеченных в конфликты. Если мафия убила человека, вовлеченного в конфликт, задача упрощается, поскольку после этого все точно знают одного мафиози, и на его устранение тратится один день вместо двух. Взяв же случай, когда мафия так не делает, мы обнаруживаем, что задача сводится к аналогичной для числа m-1. Делает - сводится сразу к аналогичной для m-2 за меньшее число ходов. Причем, как легко убедиться, в случае m=1 n=5, реализация указанного алгоритма ведет к победе города. А в случае m=1 n=4, все зависит от того, кто будет убит на суде, - вероятность 50 на 50.

Легко заметить, что эта выигрышная стратегия на самом деле - грязный хак механики игры, поскольку использует наличие у каждого игрока уникального элемента из фиксированного множества, который однозначно связан с его ролью. Нарушение любого из этих двух условий дает мафии шанс на победу. Например, если игроки получат возможность обменяться информацией только после того, как мафия убьет одного человека, и карты убитых ни ночью, ни днем, не вскрываются, множество перестает быть фиксированным. Существует шанс, что один и только один из мафиози угадает карту убитого, оказавшись, таким образом, вне конфликтов. И применить алгоритм будет невозможно, причем об этом станет известно сразу же. Точно так же, если раздавать не игральные карты, а совершенно одинаковые бумажки с совершенно одинаковыми крестиками, стратегия с самого начала становится невозможной, поскольку отсутствует уникальность элемента.

Что меняет включение в игру других ролей?

- Комиссар ничего не меняет, потому что если комиссаром назвались двое, невозможно сразу же точно выбрать из них настоящего, а мафия, зная комиссара, может убить его прежде, чем он кого-то проверит.
- Доктор понятным образом может замедлить сокращение популяции мирных, но не оказывает критичного влияния на ход рассуждений.
- Касательно маньяка, все зависит от его условий победы. Если маньяк побеждает вместе с городом, то пока он жив, можно полностью ликвидировать один конфликт за то время, пока мафия убивает одного человека. Но только один раз, если маньяк назвался честно. Если маньяк, как и мафия, шифруется, мафия знает его не точно, а с точностью до двух человек.

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

P.P.S. Мне подсказали, что
выигрышная стратегия гарантирует победу только если ей следовать. Наличие хотя-бы одного мирного, который соврал, называя свою карту, приведет к тому, что конфликтов может оказаться все-равно m, но один мафиози, назвавший карту данного большого и зеленого овоща, не вовлечен ни в один из них. Таким образом, город проиграет, но узнает об этом только в конце. Троллям на заметку.

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

Под записями о разрешении короткоствольного огнестрельного оружия (далее короткоствол) ОБЯЗАТЕЛЬНО всплывает хомячок со словами: "Власть никогда не разрешит пестики, потому что боится самосуда".

Например (курсивом мои комментарии)
"А вот самосуд — это уже серьёзно. Сбил чиновник пару человечков насмерть, нагло нарушая ПДД — а третий (подранок, типа, муж одной только что убитой и отец другой и просто хороший человек...) вместо того, чтобы медленно подыхать тут же на дороге, типа из последних сил вытянул из кобуры этот самый «пестик», пафосно превозмогая доковылял на адреналине до авто убиийцы, буксующего на обочине не иначе как в ожидании нашего героя, и разрядил в этого самого убийцу всю обойму которой у пистолета нет, зато как пафосно звучит. Возможно даже, так, чтобы не убить, но надёжнейшим образом посадить в инвалидное кресло слюшай снайпер, да.

И никакого тебе условного срока в восемь лет, никакого УДО прямо из СИЗО и т.д., и т.п.. А твёрдая точка в деле прямо на месте.

Вот ПОЭТОМУ «пестики» и не разрешают. Во избежание, так сказать."

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

Read more...Collapse )

Tags:

Profile

nik_pog
nik_pog

Latest Month

November 2020
S M T W T F S
1234567
891011121314
15161718192021
22232425262728
2930     

Syndicate

RSS Atom

Comments

Powered by LiveJournal.com
Designed by Tomohito Koshikawa