Аладдин находится в подземелье, состоящем из девяти одинаковых залов, причем он не знает, в каком именно. Если он потрет волшебную лампу, Большой Джинн перенесет его в другой зал в соответствии со схемой на левом рисунке. Если Аладдин потрет волшебное кольцо, Маленький Джинн перенесет его в соответствии со схемой на правом рисунке.
Какую последовательность действий с лампой и кольцом надо проделать Аладдину, чтобы он мог утверждать, что находится в центральном зале? Выполнять какие-либо другие действия, например, ставить отметки в залах не разрешается. Схемы перемещения Аладдину известны.
Задача имеет много решений. Приведем два решения, одно из которых структурное, а второе самое короткое из найденных участниками олимпиады.
Первое решение. Занумеруем залы в следующем порядке:
1 | 2 | 3 |
4 | 5 | 6 |
7 | 8 | 9 |
Если использовать лампу 3 раза (ллл), то Аладдин окажется в одном из залов 4, 5, 7, 8 независимо от того, где он находился первоначально:
1 | 2 | 3 |
· | · | 6 |
· | · | 9 |
Применив 3 раза кольцо и три раза лампу (ккк ллл), Аладдин окажется в одном из залов 4, 5, 7:
1 | 2 | 3 |
· | · | 6 |
· | 8 | 9 |
Повторив комбинацию (ккк ллл) еще два раза, Аладдин окажется последовательно в одном из залов 5 или 7, а затем в зале 5:
|
|
Таким образом, последовательность действий
приводит к цели.
Второе решение. К цели приводит последовательность из 13 ходов:
Например,
или