Провода через трубу

[Harut]

Здорова, народ! У меня возник вопрос по задаче, которая когда-то была на всесоюзной олимпиаде.

Четыре одинаковых провода заключены в трубу, идущую с третьего на четвертый этаж здания. Провода выступают из трубы на каждом из этих этажей. Провода пронумерованы на концах, выступающих на третьем этаже. Необходимо проставить эти же номера на концах, выступающих на четвертом этаже. Как, имея в своем распоряжении батарейку, лампочку, короткий кусок провода и совершив наименьшее число проб, установить, какой номер соответствует каждому из концов на четвертом этаже?

Можно ли решить так: соединим проволокой провода 1,2,3 на третьем этаже и подключим батарейку между (123) и 4. Поднимемся вверх и когда загорится лампочка, тогда идентифицируем четвертый провод. Потом соединим провода 1,2 и подключим батарейку между (12) и 3. Так мы идентифицируем третий провод. А потом уже подключим батарейку между 2 и 3, таким образом идентифицируем 2 провод. Ну что, народ?

[arseniiv]

Зависит от того, что можно делать с тем коротким куском провода и можем ли мы делать на проводах временные пометки (до того как точно знаем, что это конец такого-то провода). Потому что если например мы не можем соединять 1, 2, 3 с этим куском и подключать его при этом ещё и к полюсу батарейки, то временные пометки нам понадобятся, и с ними мы кстати обойдёмся двумя операциями: 1 с 2 → пометили два провода 12 и 21, 1 с 3 → теперь узнаём, кто из них 1, 2 и 3, и потому также и 4. И ещё не очень ясно, количество каких в точности операций предлагают минимизировать — тестов лампочкой? Подключений батарейки выходит 2 или 3, и без временных пометок 3 — минимум (потому что проводов 3 + 1).

[EUgeneUS]

arseniiv
Видимо, надо минимизировать хождения по этажам.

У меня получилось на третьем этаже нужно появиться три раза (последний, чтобы вернуть, как было. Можно его не считать), на четвертом - два раза.
Временных пометок не нужно.

[Dmitriy40]

У меня в точности как у EUgeneUS.
Причём так можно разметить даже 5 проводов, а не 4.
UPD. Ошибся.

[Батороев]

"Батарейка, лампочка, кусочек провода" - эквивалент омметра ("прозвонки").
1) Сделав наверху скрутку из двух проводов, прозваниваем внизу. Получаем два, которые "звенят" и два "не звенят".
2) Разбираем скрутку 1) и один из проводов скручиваем с одним из нескрученных в 1). Прозванивая внизу, обнаруживаем, что один из "не звеневших" в 1) продолжает "не звенеть" - это будет провод №1. Тот, который "не звенел" в 1), а теперь "зазвенел", будет №2. Тот, который "звенел" в 1), но перестал в 2) - №3. Тот, который "звенел" в 1) и продолжает в 2) - №4.

[Emergency]

Если труба стальная, то это уже помеченный пятый провод, что поможет не запутаться при беготне по этажам. Но так, наверное, не интересно.

[EUgeneUS]

Я знаю, как этими средствами за два похода наверх (к неразмеченным концам) разметить восемь проводов, но потребуются пометки проводов на первом шаге.
Четыре можно разметить без промежуточных пометок.

[Harut]

Всем спасибо за ответы.

arseniiv Соединять сразу 1,2,3 с проволокой можно. Вроде в авторском решении именно так и сделано.

EUgeneUS В моем случае получилось, что мы поднимаемся на четвертый этаж 3 раза и спускаемся на третий этаж 2 раза.

[EUgeneUS]

Батороев
В Вашем алгоритме для разметки 4-х проводов требуются промежуточные пометки.

-- 31.03.2021, 09:00 --

Harut
А теперь при тех же условиях (промежуточные пометки проводов разрешены) пронумеруйте восемь проводов за два похода наверх (см. выше)

-- 31.03.2021, 09:01 --

Harut в сообщении #1512218 писал(а):

EUgeneUS В моем случае получилось, что мы поднимаемся на четвертый этаж 3 раза

Это много. Двух раз достаточно.

[Harut]

EUgeneUS
Да. Я уже догадался, что мое решение не совсем рациональное.

Кстати, вот авторское решение.
Соединить три провода на третьем этаже вместе; на четвертом этаже идентифицировать четвертый провод (две операции). Затем соединить с ним один из трех оставшихся проводов и замкнуть два оставшихся. На третьем этаже идентифицировать второй провод (две операции). Наконец, соединить один из оставшихся проводов с одним из идентифицированных. На четвертом этаже определить, какие из концов принадлежат оставшимся проводам (одна операция). Всего необходимо пять операций.

[EUgeneUS]

UPD: и тринадцать проводов за два похода можно разметить. И вообще сколь угодно большое число
С пометками, конечно.

-- 31.03.2021, 09:12 --

Harut
Как автор считает "операции" не очень понятно.

[Harut]

EUgeneUS
Если честно, я тоже не понимаю.

[EUgeneUS]

Похоже, автор под "операцией" понимает одни факт измерения, и не считает за "операции" скрутку и подъем на 4-й этаж.
Тогда получается его решение.

[Harut]

EUgeneUS
А зачем нам нужна проволока? Ведь можно скрутить провода и все.))

[EUgeneUS]

Harut
Наверное, чтобы подключить батарейку к лампочке