Загадка
Давайте тоже что ли замутим.
Конкурс затяжной. Загадываем загадку (задачку). Кто дает правильный ответ, загадывает свою загадку. И так далее.
Вот загатка рас:
Две ноги на трех ногах,
А четвертая в зубах.
Вдруг четыре прибежали
И с одною убежали.
Подскочили две ноги,
Подхватили три ноги,
И тремя по четырем.
Но четыре завизжали
И с одною убежали.
Я так понял минимальное сокращение будет - 1 человек с вероятностью (n-1)/n и 0 человек с вероятностью 1/n?
Ежели так - жду до понедельника. Потом выложу решение.
Ежели так - жду до понедельника. Потом выложу решение.
Да, верно.
Сначала все договариваются между собой какому цвету какое число соответствует от 0 до N-1.
Затем встают в очередь.
Последний (назовём его "нулевой") считает CRC0 = (C1+...+Ck) mod N. Где C1, CK - номера цветов шляп людей перед ним, mod - остаток от деления. Получает некое число от 0 до N-1 и говорит цвет соответствующий этому числу. Все впередистоящие запоминают число соответствующее этому цвету.
Далее первый считает CRC1 = (C2+...+Ck) mod N. Высчитывает цвет своей шляпы как C1 = (CRC0 - CRC1) mod N. И озвучивает его.
Все оставшиеся услышав C1 рассчитывают CRC1 = (CRC0 - C1) mod N. CRC0 - сказал нулевой, C1 - первый. Далее они запоминают CRC1 вместо CRC0.
И т.д.
Последний слышит Ck-1, высчитывает CRCk-1 = (CRCk-2 - Ck-1) mod N. И называет CRCk-1, т.к. это цвет его шляпы (CRCk == 0).
В результате 1ый...kый остаются работать. 0ой с вероятностью 1/N - тоже. Но есть нет - остальные каждый день скидываются ему на хлебушек с маслицем :).
Сначала все договариваются между собой какому цвету какое число соответствует от 0 до N-1.
Затем встают в очередь.
...
Абсолютно верно. Ну за исключением имени переменной. Это, всеж таки, не CRC :-)
Эти трое знают, что доброжелателем, оплатившим обед мог быть один из них, но мог быть и кто-то другой. Они хотят выяснить, действительно ли заплатил за обед один из них, или это дело рук кого-то другого. Но при этом они очень тактичны, так что, если заплатил один из них, они не хотят, чтобы другие двое об этом узнали. Поэтому они не могут, скажем, просто договориться, что тот из них, кто заплатил (если есть такой), признается в этом.
Могут ли они выяснить, заплатил ли один из них, не выдавая при этом самим себе информацию о том, кто именно?
Это задача называется "обедающие криптографы", ее придумал и решил David Chaum в 1988м. Решение такое:
Каждый из них кидает монетку и показывает результат (орёл или решка) своему соседу справа. Таким образом есть три броска монетки, и каждый криптограф знает результат двух из них (той, что он сам бросил, и той, что бросил его сосед слева и показал ему результат). Далее, каждый из них говорит вслух следующую информацию: одинаковые два результата он видел, или разные (например, если у него вышел орёл, а у соседа слева решка, он говорит "разные"; если у него решка, и у соседа слева решка, говорит "одинаковые", итп.) — но с одним исключением: тот из них, который заплатил за обед (если есть такой) говорит наоборот, т.е. если он видит два разных результата, говорит "одинаковые", если видит два одинаковых, говорит "разные".
Этот алгоритм позволяет им определить, заплатил ли кто-то из них за обед, но вместе с тем не позволяет им (тем, кто не платил) узнать, кто именно.
Если все трое говорят правду, т.е. никто из них не платил за обед, то количество ответов "одинаковые" обязательно будет нечётным (например, 3, если у всех выпала решка, или 1, если выпал один орёл и две решки, итд.). Если же один из них заплатил, то он говорит наоборот, и это меняет количество ответов "одинаковые" на единичку, поэтому их теперь будет чётное число. Таким образом, чётное число ответов "одинаковые" прозвучало, или нечётное, позволяет определить, платил за обед кто-то из них, или другой незнакомец.
Теперь о том, почему это не даёт им никакой новой информации о том, кто заплатил за обед. Если за обед заплатил кто-то другой, то понятно, что они узнали об этом и всё. Если за обед заплатил один из них, то сам он об этом знает, остаётся доказать, что не знают двое других. Предположим, я — один из тех, кто не заплатил. Есть два варианта: либо я видел два одинаковых результата, либо два разных.
Предположим, я видел два одинаковых результата, скажем, два орла. Т.к. число ответов "одинаковые" было чётным, ещё один криптограф, кроме меня, ответил "одинаковые", а третий ответил "разные". Я не знаю результата той монетки, которую видели второй и третий. Если она выпала орлом, то второй говорил правду, а третий врал, и значит, он оплатил обед; если решкой, то второй врал, а третий говорил правду, значит, второй заплатил за обед. Но т.к. результат падения монетки был случайным, у меня нет никакой информации, позволяющей выбрать между этими двумя исходами — я знаю не больше, чем раньше, о том, кто из них мог заплатить.
Совершенно симметричный этому аргумент проходит в том случае, когда я видел два разных результата.
зИнаю :D:D:D
Это задача называется "обедающие криптографы", ее придумал и решил David Chaum в 1988м. Решение такое:
Каждый из них кидает монетку и показывает результат (орёл или решка) своему соседу справа. Таким образом есть три броска монетки, и каждый криптограф знает результат двух из них (той, что он сам бросил, и той, что бросил его сосед слева и показал ему результат). Далее, каждый из них говорит вслух следующую информацию: одинаковые два результата он видел, или разные (например, если у него вышел орёл, а у соседа слева решка, он говорит "разные"; если у него решка, и у соседа слева решка, говорит "одинаковые", итп.) — но с одним исключением: тот из них, который заплатил за обед (если есть такой) говорит наоборот, т.е. если он видит два разных результата, говорит "одинаковые", если видит два одинаковых, говорит "разные".
Этот алгоритм позволяет им определить, заплатил ли кто-то из них за обед, но вместе с тем не позволяет им (тем, кто не платил) узнать, кто именно.
Если все трое говорят правду, т.е. никто из них не платил за обед, то количество ответов "одинаковые" обязательно будет нечётным (например, 3, если у всех выпала решка, или 1, если выпал один орёл и две решки, итд.). Если же один из них заплатил, то он говорит наоборот, и это меняет количество ответов "одинаковые" на единичку, поэтому их теперь будет чётное число. Таким образом, чётное число ответов "одинаковые" прозвучало, или нечётное, позволяет определить, платил за обед кто-то из них, или другой незнакомец.
Теперь о том, почему это не даёт им никакой новой информации о том, кто заплатил за обед. Если за обед заплатил кто-то другой, то понятно, что они узнали об этом и всё. Если за обед заплатил один из них, то сам он об этом знает, остаётся доказать, что не знают двое других. Предположим, я — один из тех, кто не заплатил. Есть два варианта: либо я видел два одинаковых результата, либо два разных.
Предположим, я видел два одинаковых результата, скажем, два орла. Т.к. число ответов "одинаковые" было чётным, ещё один криптограф, кроме меня, ответил "одинаковые", а третий ответил "разные". Я не знаю результата той монетки, которую видели второй и третий. Если она выпала орлом, то второй говорил правду, а третий врал, и значит, он оплатил обед; если решкой, то второй врал, а третий говорил правду, значит, второй заплатил за обед. Но т.к. результат падения монетки был случайным, у меня нет никакой информации, позволяющей выбрать между этими двумя исходами — я знаю не больше, чем раньше, о том, кто из них мог заплатить.
Совершенно симметричный этому аргумент проходит в том случае, когда я видел два разных результата.
все это от большого ума.
им надо было по очереди опускать спички в темный мешок. тот, кто платил - кидает ломаную спичку. потом вытряхивают результат на стол, и долго думают. :)
им надо было по очереди опускать спички в темный мешок. тот, кто платил - кидает ломаную спичку. потом вытряхивают результат на стол, и долго думают. :)
Эта задача больше про алгоритмы, чем про людей :-)
Не нужно производить действий, незаметных для других (ломать спичку), все открыто и на виду.
Не нужно производить действий, незаметных для других (ломать спичку), все открыто и на виду.
это задача о том, что если постараться - все можно сделать через левое ухо :)