http://elementy.ru/problems/681 - вот еще вариант, где расписан алгоритм, но я не очень поняла, как он работает
Докажем, что после этой серии ходов принцесса обязательно будет обнаружена. Действительно, если принцесса в первую ночь была в спальне с чётным номером и трубадур её не нашел сразу же, то она находилась правее второй спальни. С каждым из первых 14 ходов трубадур «перемещался» на одну комнату вправо. При этом, очевидно, каждую ночь он стучался в спальню с той же чётностью, что и та, в которой в этот момент ночевала принцесса. Значит, они не могли разминуться и принцесса не могла оказаться левее него. Таким образом, если после 15 ночей принцесса не была обнаружена, то она не могла в первую ночь быть в спальне с чётным номером. То есть трубадур теперь точно знает, что принцесса ночевала в первую ночь в спальне с нечётным номером, и следовательно, 15-ю ночь она провела также в спальне с нечетным номером. При этом сам он только что проверил чётную спальню №16. Значит, ему нужно поменять чётность — еще раз проверить эту же спальню — и только после этого начать смещаться влево. Поскольку уже известно, что принцесса слева от него и в спальне с той же чётностью, то в какую-то из следующих 15 ночей она будет непременно обнаружена.