|
|
 |
Условие
В строку записаны в некотором порядке натуральные числа от 1 до 1993. Над строкой производится следующая операция: если на первом месте стоит число k, то первые k чисел в строке переставляются в обратном порядке. Докажите, что через несколько таких операций на первом месте окажется число 1.
Решение
Индукцией по n докажем это утверждение для строки, в которую записаны числа от 1 до n.
База. При n = 1 на первом месте уже стоит число 1.
Шаг индукции. Если в результате применения описанных операций к строке из n чисел число n окажется на последнем месте, то к первым n – 1 числам можно применить предположение индукции, так как число n уже никуда не переместится.
Если же число n никогда не окажется на последнем месте, то оно не окажется и на первом месте. Значит число, находящееся на последнем месте, никуда не перемещается. Поэтому, поменяв местами число n и число, стоящее на последнем месте, мы никак не изменим происходящего. Но теперь к первым n – 1 числам можно применить предположение индукции.
