Пароли

Ночь. Тишина. Советская ракетная шахта. Часовой на КПП спрашивает у всех пароль. Система такая: часовой называет одно число, проходящий - другое. В кустах лежит американский шпион и слушает.

Идёт первый солдат.
Часовой: 28.
Солдат: 14.
Часовой: Проходи.

Идёт второй солдат.
Часовой: 22.
Солдат: 11.
Часовой: Проходи.

ЧукчаШпион был не дурак, поднялся с земли, гордо пошёл к посту.
Часовой: 42.
Шпион: 21.
Часовой: Попался! Надо было отвечать 8!

Вопрос: какая система получения отзыва по паролю?

Задача Ландау

Продолжите ряд букв: Р Д Т Ч П ...

Рассказывают, что Лев Ландау давал эту задачу на вступительных экзаменах в аспирантуру. При этом он считал, что решить её может либо идиот, либо гений. О гениальном студенте Ландау, конечно же, знал бы по его научным достижениям, поэтому решивших эту задачу он в аспирантуру не брал.

К сожалению, когда мне впервые дали эту задачку (а было это в Буревестнике в 2007 году), я об этой истории не слышал, и нашёл ответ. Даже и не знаю, что теперь думать.

Список с петлёй

У Вас есть указатель на первый элемент односвязного списка. Этот список может либо заканчиваться указателем на null, либо содержать петлю, т.е. ссылка из очередного элемента может указывать на один из предыдущих элементов (в том числе и на тот же самый элемент).

Примеры двух списков на рисунке:

За линейное время и константную память необходимо проверить, есть ли в списке петля. Количество элементов в списке заранее не известно.

25 лошадей

В вашем распоряжении ипподром с пятью дорожками, а также 25 лошадей, каждая из которых может пробежать круг за определённое время (время круга у всех лошадей различается). К сожалению, у Вас нет секундомера, поэтому Вы можете только устраивать забеги из пяти участников и смотреть, в каком порядке они придут финишу.

За какое минимальное число забегов можно определить тройку призёров, т.е. три лошади, которые пробегают дистанцию быстрее остальных?

Автобус на неровной дороге

Дорога из пункта А в пункт Б идёт то в гору, то под гору, а горизонтальных участков нет совсем. В гору автобус едет со скоростью 30 км/ч, а под гору он развивает скорость 60 км/ч. Автобус совершил рейс из А в Б и обратно. Какова была его средняя скорость?

7 гирек

Можно ли заказать набор из семи таких гирек, чтобы ими можно было взвесить любой слиток золота весом от 1 грамма до 1 килограмма? Слиток золота весит целое число грамм, гирьки можно класть на обе чаши весов.

Эту задачу мой младший брат решал на собеседовании в Abbyy.