Летопись: 21 декабря 2011

85-е заседание клуба "Эратосфен". 28 декабря 2011 года, среда, 13 часов.

А.Ю.Алексеев: "Алгоритмические" задачи- 4.
Несколько раз на своих заседаниях мы обсуждали решения замечательных "алгоритмических" задач, вызвавших большой интерес гимназистов, выпускников и учителей. (Тексты старых задач можно посмотреть на сайте гимназии в "Летописи" от 16 ноября 2007 года, 10 мая и 26 декабря 2010 года.) Предлагаем вашему вниманию условия двух новых задач из нашей коллекции:

1. Задача про кота и мышку. Есть n подряд идущих норок, вот так: ООО...ОО. В одной из них сидит мышка. Кот пытается поймать мышку по следующим правилам. Он сует лапу в какую-то норку; если он попал в норку с мышкой, то съедает ее и игра заканчивается. Если не попал, мышка обязательно перебегает под землей из своей норки в одну из соседних. Норки не закольцованы, то есть из первой можно попасть только во вторую, а из n-й только в (n-1)-ю. Затем снова наступает черед кота и т. д.
Вопрос: как действовать коту, чтобы наверняка поймать мышку? За сколько ходов он может это сделать? (Пятиклассникам: решите задачу для n=5.)

2. Задача про джип. Джипу нужно преодолеть пустыню длиной 1000 км. На 1 км пути он тратит 1 л бензина, но может везти с собой не более 500 л бензина (в бензобаке и в канистрах). В любой точке пустыни можно сделать склад: оставлять бензин в канистрах, а затем забирать его. Количество бензина на базе (в точке старта) не ограничено, канистры могут быть любой емкости. Каково минимальное количество истраченного за весь маршрут бензина (или, что то же самое, минимальное количество пройденных километров)?

Внимание! Тот, кто изложит перед публикой правильное решение хотя бы одной из двух задач, получит приз от клуба "Эратосфен"!

Затем поздравления, праздничное чаепитие, интеллектуальные игры "Новый Элевсин", "Set" и другие.
Ждем всех желающих!

?