Небольшая интересная задача на логику. Задача с собеседований про электрика, реку и 49 проводов.
Поперек реки на ее дне лежит кабель. Он состоит из 49 изолированных проводов одинакового цвета, из-за чего внешне отличить их друг от друга невозможно. Задача электрика - пронумеровать концы проводов числами от 1 до 49, конечно же, чтобы числа на соответствующих концах совпали. В его распоряжении для этого есть катер, источник тока и прибор-индикатор, показывающий, есть ли напряжение в проводе.
Какое минимальное количество переправ нужно сделать электрику, чтобы выполнить поставленную задачу?
Решение
Стоя на берегу (допустим, электрик находится на левом), он должен на любой из проводов подать напряжение. Отмечает его числом “1”. Другие 48 проводов соединяет между собой попарно: в итоге получается 24 пары.
Дальше электрик забирается в катер и плывет на правый берег. Там он с помощью измерительного прибора находит провод, который под напряжением - провод “1” - и отмечает его цифрой.
Теперь он соединяет первый провод с любым другим и ставит на нем цифру “2”. Мы помним, что на левом берегу провода попарно соединены между собой, значит, ток пройдет по проводу “2” и вернется на правый берег, где стоит электрик, по тому проводу, с которым он соединен на левом. Новый провод, в котором вернулся ток, электрик помечает цифрой “3”. Таким же образом он продолжает нумеровать оставшиеся провода на правом берегу (“3” соединяет с “4”, в каком проводе ток вернулся, тот значит “5” и т.д.).
Когда все провода на правом берег пронумерованы, электрик во второй раз садится в катер и возвращается на левый берег. Там он видит изначально подписанный провод “1” и начинает методом перебора искать соединение между проводами “2” и “3”. Только если разъединить именно эти два провода, пропадет ток во всех остальных, кроме “1” и “2” (если при разъединении проводов ток в других не исчезает, значит, это не те провода, поэтому он соединяет их обратно и продолжает поиски). Когда ключевая пара найдена, электрик ставит цифру “2” на проводе, который остался под напряжением, и “3” на том, который составлял ему пару и остался без напряжения.
Затем электрик вновь соединяет второй и третий провода, и используя такую же логику, с помощью которой он их обнаружил, находит и пронумеровывает все остальные.
Ответ
Минимальное количество переправ, которые нужно сделать электрику, чтобы решить задачу, - две.