ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 64646
Тема:    [ Теория алгоритмов (прочее) ]
Сложность: 3+
Классы: 8,9
В корзину
Прислать комментарий

Условие

На переправу через пролив Босфор выстроилась очередь: первый Али-Баба, за ним 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-м.


Ответ

Смогут.

Замечания

1. Второй способ гораздо выгоднее: требуется всего 153 рейса, а при первом способе – более 800.

2. Баллы: 8-9 кл. – 6, 10-11 кл. – 5.

Источники и прецеденты использования

олимпиада
Название Турнир городов
Турнир
Номер 35
Дата 2013/2014
вариант
Вариант весенний тур, базовый вариант, 10-11 класс
задача
Номер 3
олимпиада
Название Турнир городов
Турнир
Номер 35
Дата 2013/2014
вариант
Вариант весенний тур, базовый вариант, 8-9 класс
задача
Номер 5

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .