Apr. 2nd, 2012

spamsink: (Default)
О садовых шлангах

Алиса и Боб живут по разные стороны от забора. Алиса задумала 5-битовое число и Боб задумал 5-битовое число. Им нужно узнать, совпадают ли их числа, ничего не говоря друг другу.
Под забором с одного участка на другой идут 8 труб, концы которых они могут - каждый на своем участке - соединять шлангами (без разветвлений). На Алисином участке есть кран, который можно подключить к одной из труб. Задача заключается в нахождении 32 пар конфигураций подключения шлангов (для каждого из чисел 0-31 что должна делать Алиса и что должен делать Боб), таких, чтобы после открытия крана вода текла обратно на Алисин участок, если и только если их числа совпадают.

Для однобитных чисел достаточно трех труб, и решение очевидно.

Для двухбитных - для очевидного решения достаточно пяти труб, а сколько необходимо?

И т.п.
Page generated Sep. 24th, 2025 03:07 pm
Powered by Dreamwidth Studios