Метка: Кооперативные задачи

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

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

Опубликовано

Тюрьма и выключатель

Несколько человек посадили в тюрьму и рассадили по одиночным камерам. Их по одному, в тайне от остальных водят в камеру пыток, где расположен только один выключатель, имеющий два положения: «Включено» и «Выключено». Каждый из них может либо переключить выключатель, либо не трогать его. Порядок, в котором их водят в камеру, совершенно произволен, зависит только от тюремного начальства и единственное гарантированное условие — то, что любой из заключённых в конце концов окажется в камере сколь угодно большое число раз.

В любой момент любой из них может объявить «Стоп». При этом, если окажется, что каждый из группы заключённых уже побывал в камере пыток их всех отпускают, если нет — всех казнят. Как им надо договориться, чтобы гарантированно выйти на свободу?

Решение

Им надо выбрать капитана. Капитан, когда попадает в камеру пыток и видит выключатель в положении «Включено» выключает его, а иначе не трогает. Каждый из остальных переводит выключатель в положение «Включено» при первой возможности, но только два раза, а больше его не трогает. Капитану нужно насчитать 2(n - 1) - 1 включений, чтобы быть уверенным, что все его товарищи там побывали хотя бы по одному разу, не зависимо от начального положения выключателя.

Опубликовано

Три миссионера и три дикаря

Три миссионера и три дикаря-носильщика подошли к берегу реки. У них есть только одна лодка, которая вмещает двоих. Дикари слушаются миссионеров во всём, даже когда остаются одни. Но, если их число в любом месте оказывается больше числа миссионеров, есть опасность, что они могут взбунтоваться и съесть своих хозяев. Как переправиться?

Решение

\rightrightarrows миссионер + дикарь
\leftarrow миссионер
\rightrightarrows 2 дикаря
\leftarrow дикарь
\rightrightarrows 2 миссионера
\leftleftarrows миссионер + дикарь
\rightrightarrows 2 миссионера
\leftarrow дикарь
\rightrightarrows 2 дикаря
\leftarrow дикарь
\rightrightarrows 2 дикаря

Опубликовано

Разбойники и Пьяницы

Три разбойника нашли клад. У каждого из них своё собственное представление о стоимости каждой драгоценности. Как им его разделить?

И более общая формулировка:

Несколько пьяниц хотят распить в подворотне бутылку водки. У них есть только эта самая бутылка и один пустой стакан. К сожалению, у каждого из них своё собственное представление о вместительности бутылки и стакана. Если один из них считает, что в стакане меньше, чем \alpha всего объема, то другой может не согласиться и заявить, что это не так, а как раз наоборот. Тем не менее, каждый из них достаточно разумен, чтобы признать, что если из бутылки отлить меньше, чем \alpha всего объема, то в ней останется больше, чем (1 - \alpha). Как им осуществить задуманное и не переругаться между собой?

Решение

Пусть число пьяниц n. Им нужно выстроиться в очередь. Первый отливает из бутылки 1 / n eё объема и передает следующему. Каждый пьяница, когда получает стакан, должен решить: если он считает, что там не больше 1 / n, он просто передаёт стакан следующему. Если же больше, он отливает назад в бутылку избыток, так, чтобы там осталось ровно 1 / n по его мнению. Стакан выпивает последний из них, кто в него наливал или из него отливал, после этого он уходит домой спать, а остальные продолжают ту же процедуру.

Опубликовано

Гномы и людоеды

Вот такая кровожадная задачка.

Людоеды поймали несколько гномов и обещали наутро часть из них съесть. Чтобы выбрать жертв они собираются выстроить всех гномов в колонну, так чтобы первый видел всех, кроме себя, второй всех, кроме себя и первого и т.д., и надеть всем гномам шапки — белые и чёрные. После этого спросить всех по очереди, начиная с первого, какая у него на голове шапка. Если ответ будет правильный, гнома отпустят, если нет — съедят. Как гномам надо договориться, чтобы удалось спастись максимальному числу из них?

Решение

Первый гном должен сосчитать количество белых шапок, которые он видит и, если оно чётное, сказать «белая», если нечетное — «чёрная». Тогда все остальные гномы, услышав предыдущие ответы, смогут по очереди вычислить свой цвет и спасутся. Первого съедят в вероятностью 50%.