Marksman, Есть целый класс подобных задач на нахождение алгоритма несколькими участниками для совместного достижения цели в условиях ограничения обмена информации между собой. Заключенные тюрьмы в условиях таких задач фигурируют довольно часто. Вот несколько навскидку (воспроизвожу условия по памяти). Возможно, кого-нибудь заинтересует.
1. Зеки и лампочка
Начальник тюрьмы собрал заключенных и говорит: "Сыграем в игру: сейчас вы посовещаетесь между собой, а потом вас разведут по одиночным камерам, и будут раз в день выбирать одного из вас и отводить ненадолго в комнату, где есть только одна лампочка и выключатель. Во время нахождения в комнате можно включить выключенную лампочку, выключить включённую, или ничего не трогать. Каждый из вас побывает в комнате с лампочкой и неоднократно. Ваша задача такая - любой из вас зайдя в комнату может сказать охраннику "Я знаю, что в этой комнате побывали все". Если он оказывается прав, и в комнате с лампочкой к этому моменту действительно успел побывать каждый заключенный (хотя бы по разу), то вас всех освободят. Если он ошибётся, то расстреляют."
Какой алгоритм следует выработать зекам прежде чем их разведут по камерам (после этого они общаться уже не могут)?
З.Ы. Понятно, что никакого иного канала передачи информации между участниками нету (нельзя оставлять метки в комнате, царапать на стенах, перестукиваться межу камерами и т.д.). По сути лампочка представляет собой однобитный регистр или ячейку памяти, который зекам и нужно использовать для передачи информации между собой.
2. Тролль и гномы
Старая задачка для школьников средних классов. Пещерный тролль поймал некоторое количество гномов и устроил такую игру. Всех гномов он построил в шеренгу друг за другом, так чтобы каждый мог видеть только впереди стоящих, но не тех, кто у него за спиной. Каждому на голову он надел шапочку черного либо белого цветов, так чтобы каждый гном не знал, какого цвета шапочка на нём надета. Потом тролль спрашивает у стоящего последним, какого цвета шапочка на нём надета. Если гном отвечает неправильно, его съедают. Если правильно, выпускают из пещеры. Затем спрашивает следующего за ним и так далее, пока не дойдёт до самого первого, перед которым уже никого нет. Перед началом игры гномы могут посовещаться и выработать стратегию, которая позволяет спастись всем, кроме одного (у него шансы 50 на 50). В чем заключается эта стратегия?
3. Два зека и монетка.
Начальник тюрьмы говорит двум заключенным: "Сейчас вас разведут по разным камерам, а я буду подбрасывать монетку, которая с равной вероятностью может упасть орлом или решкой. Результаты бросков я запишу и передам в первую камеру. Потом я опять буду подбрасывать монетку и передам результаты подбрасываний во вторую камеру. Таким образом, у каждого из вас будет случайная последовательность орлов и решек (у каждого своя), но вы не будете знать, какая последовательность у другого. Затем каждый из вас напишет на бумажке число и отдаст мне. Например, первый напишет 5, а второй 7. А я посмотрю, что стоит на седьмом месте в последовательности, которую передали первому, и что стоит на пятом месте в последовательности, которую передали второму. Если значения совпадут (и там и там орёл, или и там и там решка), то вас обоих освободят. Перед тем как вас разведут по камерам можете посовещаться и выработать стратегию, которая даст вам максимальные шансы на освобождение".
З.Ы. По поводу длины последовательностей. Изначально в условиях фигурировали бесконечные последовательности. Но поскольку начальнику тюрьмы тяжело бросать монетку бесконечное количество раз, то обычно условие формулируется так, что полученные участниками случайные последовательности достаточно длинны, чтобы с их помощью можно было реализовать любой алгоритм, оперирующий конечными значениями. Впрочем, известные решения этой задачи вообще требуют не больше нескольких десятков бросков монеты.
З.З.Ы. На первый взгляд кажется, что тут решения не может быть, а вероятность совпадения значений в случайных последовательностях всегда 50%, но это не так.
Добавлено: [time]02 Декабря 2023, 11:21:57[/time]
нет никаких последовательных цепочек
Вот смотри. Допустим твой номер 69. Ты открываешь коробку 69, а там лежит бумажка с номером 13. Ты открываешь коробку 13, а там написано 81. Ты открываешь коробку с номером 81, а там написано 69. Всё, цепочка замкнулась. В данном случае её длина равна трём. Это значит, что заключенные с номерами 69, 13 и 81 действуя по такому алгоритму найдут свои числа всего за три попытки. Длина таких цепочек может быть разной. Крайние случаи: сто цепочек с длиной 1 (это когда все номера лежат в своих коробках и каждый найдёт свой номер с одной попытки) и одна цепочка с длиной 100 (чтобы найти свой номер придётся открыть все коробки). Но скорее всего в случайно перемешанных коробках будет несколько цепочек разной длины. Если ни одна из них не будет длиннее пятидесяти, то всё - повезло. Задача решена.
