|
|
 |
Условие
Испанский король решил перевесить по-своему портреты своих предшественников в круглой башне замка. Однако он хочет, чтобы за один раз меняли местами только два портрета, висящие рядом, причём это не должны быть портреты двух королей, один из которых царствовал сразу после другого. Кроме того, ему важно лишь взаимное расположение портретов, и два расположения, отличающиеся поворотом круга, он считает одинаковыми. Доказать, что как бы сначала ни висели портреты, король может по этим правилам добиться любого нового их расположения.
Решение
Занумеруем портреты королей по порядку их царствования: 1, 2,..., n. Покажем, как королю из любого исходного расположения портретов получить порядок 1, 2,..., n по часовой стрелке (назовём такой порядок стандартным). Подгоним сначала первый портрет ко второму (двигая первый по часовой стрелке). Мы сможем это сделать, так как первый портрет можно менять с любым, кроме второго. После этого будем двигать портреты 1 и 2 вместе, пока не подгоним их к третьему, и т. д. В результате получим стандартный порядок.
Заметим, что мы заодно научились получать из стандартного порядка любой другой порядок. Действительно, для этого достаточно проделать перевешивания, приводящие конечный порядок к стандартному, но в обратном порядке. Теперь уже несложно получить из любого порядка любой другой: надо сначала из исходного порядка получить стандартный, а потом из него получить конечный порядок.
