Задача
На переправу через пролив Босфор выстроилась очередь: первый Али-Баба, за ним 40 разбойников. Лодка одна, в ней могут плыть двое или трое (в одиночку плыть нельзя). Среди плывущих в лодке не должно быть людей, которые не дружат между собой. Смогут ли все они переправиться, если каждые двое рядом стоящих в очереди – друзья, а Али-Баба ещё дружит с разбойником, стоящим через одного от него?
Решение
Занумеруем всех разбойников в порядке очереди. Первый способ. Сначала переправляются Али-Баба и первые два разбойника, 2-й остается, а Али-Баба с 1-м возвращаются. Затем 3-й разбойник переправляется с 4-м и возвращается со 2-м (произошла замена 2-го на 4-го). Потом 5-й меняет 4-го на 6-го и т.д. Наконец, на том берегу окажется 40-й, а остальные с лодкой – еще на этом.
Забудем про 40-го разбойника и с помощью той же процедуры (со сменой чётности) переправим на тот берег 39-го. И т.д. Второй способ. За пять рейсов можно переправить основную четверку (Али-Бабу и первых трёх разбойников): сначала переправляются Али-Баба и первые два разбойника, затем 1-й и 2-й возвращаются, переправляются 2-й и 3-й разбойник, и наконец Али-Баба со 2-м возвращаются и забирают 1-го.
После этого 2-й и 3-й возвращаются, переправляются 39-й и 40-й, и Али-Баба с 1-м возвращаются. Итак, за 8 рейсов переправились последние два разбойника. За следующие 8 рейсов аналогично переправляются 37-й и 38-й, и т.д. Когда на исходном берегу останутся Али-Баба и первые четыре разбойника, снова переправляется основная четвёрка, 2-й и 3-й возвращаются, переправляются 3-й и 4-й, и Али-Баба с 1-м возвращаются за 2-м.
Ответ
Смогут.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь