Apr. 2nd, 2012

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

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

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

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

И т.п.

Profile

spamsink: (Default)
spamsink

November 2025

S M T W T F S
      1
2345678
910 11 1213 1415
16171819202122
23 242526272829
30      

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags
Page generated Nov. 30th, 2025 02:08 pm
Powered by Dreamwidth Studios