Ну и решение задачи про бесплатный обед в ресторане.
Трое человек пришли в ресторан пообедать. Уселись за стол и официант сообщает им, что их обед уже заранее оплачен.
Эти трое знают, что доброжелателем, оплатившим обед мог быть один из них, но мог быть и кто-то другой. Они хотят выяснить, действительно ли заплатил за обед один из них, или это дело рук кого-то другого. Но при этом они очень тактичны, так что, если заплатил один из них, они не хотят, чтобы другие двое об этом узнали. Поэтому они не могут, скажем, просто договориться, что тот из них, кто заплатил (если есть такой), признается в этом.
Могут ли они выяснить, заплатил ли один из них, не выдавая при этом самим себе информацию о том, кто именно?
Это задача называется "обедающие криптографы", ее придумал и решил David Chaum в 1988м. Решение такое:
Каждый из них кидает монетку и показывает результат (орёл или решка) своему соседу справа. Таким образом есть три броска монетки, и каждый криптограф знает результат двух из них (той, что он сам бросил, и той, что бросил его сосед слева и показал ему результат). Далее, каждый из них говорит вслух следующую информацию: одинаковые два результата он видел, или разные (например, если у него вышел орёл, а у соседа слева решка, он говорит "разные"; если у него решка, и у соседа слева решка, говорит "одинаковые", итп.) — но с одним исключением: тот из них, который заплатил за обед (если есть такой) говорит наоборот, т.е. если он видит два разных результата, говорит "одинаковые", если видит два одинаковых, говорит "разные".
Этот алгоритм позволяет им определить, заплатил ли кто-то из них за обед, но вместе с тем не позволяет им (тем, кто не платил) узнать, кто именно.
Если все трое говорят правду, т.е. никто из них не платил за обед, то количество ответов "одинаковые" обязательно будет нечётным (например, 3, если у всех выпала решка, или 1, если выпал один орёл и две решки, итд.). Если же один из них заплатил, то он говорит наоборот, и это меняет количество ответов "одинаковые" на единичку, поэтому их теперь будет чётное число. Таким образом, чётное число ответов "одинаковые" прозвучало, или нечётное, позволяет определить, платил за обед кто-то из них, или другой незнакомец.
Теперь о том, почему это не даёт им никакой новой информации о том, кто заплатил за обед. Если за обед заплатил кто-то другой, то понятно, что они узнали об этом и всё. Если за обед заплатил один из них, то сам он об этом знает, остаётся доказать, что не знают двое других. Предположим, я — один из тех, кто не заплатил. Есть два варианта: либо я видел два одинаковых результата, либо два разных.
Предположим, я видел два одинаковых результата, скажем, два орла. Т.к. число ответов "одинаковые" было чётным, ещё один криптограф, кроме меня, ответил "одинаковые", а третий ответил "разные". Я не знаю результата той монетки, которую видели второй и третий. Если она выпала орлом, то второй говорил правду, а третий врал, и значит, он оплатил обед; если решкой, то второй врал, а третий говорил правду, значит, второй заплатил за обед. Но т.к. результат падения монетки был случайным, у меня нет никакой информации, позволяющей выбрать между этими двумя исходами — я знаю не больше, чем раньше, о том, кто из них мог заплатить.
Совершенно симметричный этому аргумент проходит в том случае, когда я видел два разных результата.
