Олимпиада имени Леонарда Эйлера2013-2014 учебный год, IV тур дистанционного этапа

К переправе подошли царевна Соня и 7 богатырей. Богатыри выстроились в ряд так, что каждые двое рядом стоящих богатырей — друзья, богатыри, стоящие не рядом, между собой не дружат, а царевна дружит со всеми кроме среднего богатыря. Имеется одна лодка, в которой могут плыть либо двое друзей, либо трое попарно дружащих (в одиночку плыть нельзя). Смогут ли переправиться все подошедшие к переправе?

Комментарий/решение

Комментарии от администратора Комментарии от администратора №1.     Ответ. Смогут.
Решение. Обозначим $C$ царевну, и пронумеруем богатырей от 1 до 7 по порядку (Соня не дружит с 4-м). Буква и цифры обозначают, кто в лодке, стрелка $\to$ переправу на другой берег, стрелка $\leftarrow$ — путь обратно. Работает следующий алгоритм: $C12 \to$, $C1 \leftarrow$, $34 \to$, $23 \leftarrow$, $C56 \to$, $C6 \leftarrow$, $C12 \to$, $C2\leftarrow$, $C23 \to$, $C5 \leftarrow$, $C56\to$, $C6 \leftarrow$, $C67 \to$.