?

Log in

No account? Create an account

Какая задача! - Общество дровосеков Бердичева по изучению Мишны

Apr. 2nd, 2012

04:51 pm - Какая задача!

Previous Entry Share Next Entry

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

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

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

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

И т.п.

Comments:

[User Picture]
From:amigofriend
Date:April 3rd, 2012 12:25 am (UTC)
(Link)
Ишь чего задумали!
(Reply) (Thread)
[User Picture]
From:spamsink
Date:April 3rd, 2012 03:50 am (UTC)
(Link)
Алиса с Бобом (правильнее будет - с Базилио) постоянно что-нибудь задумывают.
(Reply) (Parent) (Thread)
[User Picture]
From:yatur
Date:April 3rd, 2012 02:39 am (UTC)
(Link)
Алиса продает все шланги, кроме одного, и покупает ракетницу с 33 зарядами к ней. Она открывает воду так, чтобы вода лилась на участок Боба и ждет 30 секунд (или сколько там надо, чтобы вода полилась с его стороны). После этого Алиса делает от 1 до 33 выстрела из ракетницы и выключает воду (ноль выстрелов ненадежно, так как невозможно отличить это от пропущенных выстрелов).

Боб тоже покупает ракетницу. Если число Боба совпадает, он стреляет 2 раза. В противном случае, Боб стреляет 1 раз.
(Reply) (Thread)
[User Picture]
From:spamsink
Date:April 3rd, 2012 02:56 am (UTC)
(Link)
В модельном мире никаких объектов, кроме труб, шлангов и воды, нет.
(Reply) (Parent) (Thread)
[User Picture]
From:yatur
Date:April 3rd, 2012 05:08 am (UTC)
(Link)
Ну... Тогда кидать шланг над забором. Открываем воду, кидаем шланг нужное кол-во раз, закрываем воду. Да-да, я знаю, забор высокий, шланг не добросишь :)

Тогда можно пускать модулированную струю воды вверх. Какое у них там давление в водопроводе? Пара атмосфер - уже 26 метров. Если у них там именно забор, а не Великая Китайская Стена, должно хватить.
(Reply) (Parent) (Thread)
[User Picture]
From:cema
Date:April 3rd, 2012 03:19 am (UTC)
(Link)
Напомнило фильм Brazil и как там Роберт де Ниро затыкал одну трубу другою...
(Reply) (Thread)
[User Picture]
From:strelf1
Date:April 3rd, 2012 09:23 am (UTC)
(Link)
А. и Б. сидели на трубе.
(Reply) (Thread)
[User Picture]
From:mtve
Date:April 4th, 2012 02:00 pm (UTC)
(Link)
вроде как для 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


Edited at 2012-04-04 02:46 pm (UTC)
(Reply) (Thread)