April 2nd, 2012

lenin

Another one bites the dust...

lenin

Какая задача!

О садовых шлангах

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

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

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

И т.п.