Разделы 
Дополнительно
Задача по математике - 1790
2019-01-20 
В строку записаны в некотором порядке натуральные числа от 1 до 1993. Над строкой производится следующая операция: если на первом месте стоит число $k$, то первые $k$ чисел в строке переставляются в обратном порядке. Докажите, что через несколько таких операций на первом месте обязательно окажется число 1.
Решение:
Требуемое утверждение докажем индукцией по количеству $n$ чисел в строке (в условии задачи взято $n = 1993$).
При $n = 1$ на первом месте стоит число 1. Пусть теперь для строки из $n - 1$ чисел утверждение доказано. Докажем его для строки из $n$ чисел. Если в результате выполнения описанных в условии операций число $n$ окажется на последнем месте, то к первым $(n - 1)$ числам сразу можно применить предположение индукции, так как число $n$ уже никуда не переместится.
Если же число $n$ никогда не окажется на последнем месте, то оно не окажется и на первом месте. Но тогда число, находящееся на последнем месте, никуда не перемещается. Поэтому, поменяв местами число $n$ и число, стоящее на последнем месте, мы никак не изменим происходящего. Следовательно, к первым $(n - 1)$ числам можно применить предположение индукции.
В строку записаны в некотором порядке натуральные числа от 1 до 1993. Над строкой производится следующая операция: если на первом месте стоит число $k$, то первые $k$ чисел в строке переставляются в обратном порядке. Докажите, что через несколько таких операций на первом месте обязательно окажется число 1.
Решение:
Требуемое утверждение докажем индукцией по количеству $n$ чисел в строке (в условии задачи взято $n = 1993$).
При $n = 1$ на первом месте стоит число 1. Пусть теперь для строки из $n - 1$ чисел утверждение доказано. Докажем его для строки из $n$ чисел. Если в результате выполнения описанных в условии операций число $n$ окажется на последнем месте, то к первым $(n - 1)$ числам сразу можно применить предположение индукции, так как число $n$ уже никуда не переместится.
Если же число $n$ никогда не окажется на последнем месте, то оно не окажется и на первом месте. Но тогда число, находящееся на последнем месте, никуда не перемещается. Поэтому, поменяв местами число $n$ и число, стоящее на последнем месте, мы никак не изменим происходящего. Следовательно, к первым $(n - 1)$ числам можно применить предположение индукции.
