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

[spamsink]

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

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

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

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

И т.п.

Comments

[amigofriend.livejournal.com]

Ишь чего задумали!

[spamsink]

Алиса с Бобом (правильнее будет - с Базилио) постоянно что-нибудь задумывают.

[yatur.livejournal.com]

Алиса продает все шланги, кроме одного, и покупает ракетницу с 33 зарядами к ней. Она открывает воду так, чтобы вода лилась на участок Боба и ждет 30 секунд (или сколько там надо, чтобы вода полилась с его стороны). После этого Алиса делает от 1 до 33 выстрела из ракетницы и выключает воду (ноль выстрелов ненадежно, так как невозможно отличить это от пропущенных выстрелов).

Боб тоже покупает ракетницу. Если число Боба совпадает, он стреляет 2 раза. В противном случае, Боб стреляет 1 раз.

[spamsink]

В модельном мире никаких объектов, кроме труб, шлангов и воды, нет.

[yatur.livejournal.com]

Ну... Тогда кидать шланг над забором. Открываем воду, кидаем шланг нужное кол-во раз, закрываем воду. Да-да, я знаю, забор высокий, шланг не добросишь :)

Тогда можно пускать модулированную струю воды вверх. Какое у них там давление в водопроводе? Пара атмосфер - уже 26 метров. Если у них там именно забор, а не Великая Китайская Стена, должно хватить.

[cema.livejournal.com]

Напомнило фильм Brazil и как там Роберт де Ниро затыкал одну трубу другою...

[strelf1.livejournal.com]

А. и Б. сидели на трубе.

[mtve.livejournal.com]

вроде как для 6 чисел достаточно четырёх труб

(-1 это кран, 0 это не подключенная труба):

-1 0 4 3 : 2 1 0 0
-1 3 2 0 : 4 0 0 1
-1 4 0 2 : 3 0 1 0
3 -1 1 0 : 0 4 0 2
4 -1 0 1 : 0 3 2 0
2 1 -1 0 : 0 0 4 3

а для трёх бит необходимо и достаточно пяти труб

-1 0 0 5 4 : 2 1 0 0 0
-1 4 0 2 0 : 5 0 0 0 1
-1 5 0 0 2 : 4 0 0 1 0
3 -1 1 0 0 : 0 4 0 2 0
4 -1 0 1 0 : 0 3 2 0 0
0 4 -1 2 0 : 0 0 5 0 3
0 5 -1 0 2 : 0 0 4 3 0
3 0 1 0 -1 : 0 0 0 5 4