Пару месяцев назад я придумал одну задачу. Рассказал ее коллеге, и мы вместе нашли некое подобие решения. Теперь мне бы хотелось услышать какие-либо новые идеи.
Условие: Алиса и Боб загадали по однобайтовому числу (пусть эти числа будут называться a и b соответственно). Требуется придумать протокол общения между Алисой и Бобом, позволяющий им понять: равны ли a и b? При этом хочется, чтобы Алиса и Боб выдали друг другу как можно меньше информации о своих числах (в идеале — только сам факт равенства/неравенства). Предполагается, что Алиса и Боб будут строго следовать протоколу. Предполагается, что посторонних участников в задаче нет.
Прошу писать идеи решения в комментариях и прятать их под спойлеры.
UPD. hellman_ предложил решение, которое на первый взгляд удовлетворяет вышеописанному требованию к идеальному решению.
UPD3. Опубликовал неидеальное авторское решение.
