Разделы 
Дополнительно
Задача по математике - 3374
2019-06-03 
Каждый зритель, купивший билет в первый ряд кинотеатра, занял одно из мест в первом ряду. Оказалось, что все места в первом ряду заняты, но каждый зритель сидит не на своем месте. Билетер может менять местами соседей, если оба сидят не на своих местах. Всегда ли он сможет рассадить всех на свои места?
Решение:
Занумеруем всех зрителей номерами их билетов $1, \cdots, n$. Пусть, для определенности, самое правое место имеет номер $n$, а самое левое - номер 1. Мы сведем задачу к той же задаче с меньшим числом зрителей, пересадив зрителя $n$ на свое место.
Пусть билетер действует следующим образом. Он пересаживает зрителя $n$ вправо, если его правый сосед при этом не садится на свое место. Если зрителя $n$ не удается пересадить правее места $k$, то на $(k + 1)$-м месте сидит зритель $k$. Выберем наибольшее $m$ такое, что зрители с номерами $k, k + 1, \cdots, k + m - 1$ сидят на местах $k + 1, k + 2, \cdots, k + m$ соответственно. Возможны два случая: $k + m < n$ или $k + m = n$.
В первом случае на $(k + m + 1)$-м месте сидит зритель $j, j = k + m$. Ясно, что $j = k + m - 1$, $j = k + m - 2, \cdots, j = k + 1$.
Поэтому можно пересадить зрителя $j$ налево, потом еще раз налево и т. д., пока он не поменяется местами со зрителем $n$. В результате билетеру удастся пересадить зрителя $n$ на одно место правее, причем все зрители слева от $n$ сидят на чужих местах. Билетер может повторять эту процедуру до тех пор, пока не произойдет одно из двух: зритель $n$ окажется на своем месте или встретится второй случай ($k + m = n$).
Во втором случае билетер может рассадить по своим местам зрителей $k, k +1, \cdots, n$, пересаживая зрителя $n$ вправо до его места.
Таким образом, несколько зрителей в правом конце ряда будут сидеть на своих местах, а остальные - нет. Мы свели задачу к исходной с меньшим числом зрителей.
Ответ: Всегда.
Каждый зритель, купивший билет в первый ряд кинотеатра, занял одно из мест в первом ряду. Оказалось, что все места в первом ряду заняты, но каждый зритель сидит не на своем месте. Билетер может менять местами соседей, если оба сидят не на своих местах. Всегда ли он сможет рассадить всех на свои места?
Решение:
Занумеруем всех зрителей номерами их билетов $1, \cdots, n$. Пусть, для определенности, самое правое место имеет номер $n$, а самое левое - номер 1. Мы сведем задачу к той же задаче с меньшим числом зрителей, пересадив зрителя $n$ на свое место.
Пусть билетер действует следующим образом. Он пересаживает зрителя $n$ вправо, если его правый сосед при этом не садится на свое место. Если зрителя $n$ не удается пересадить правее места $k$, то на $(k + 1)$-м месте сидит зритель $k$. Выберем наибольшее $m$ такое, что зрители с номерами $k, k + 1, \cdots, k + m - 1$ сидят на местах $k + 1, k + 2, \cdots, k + m$ соответственно. Возможны два случая: $k + m < n$ или $k + m = n$.
В первом случае на $(k + m + 1)$-м месте сидит зритель $j, j = k + m$. Ясно, что $j = k + m - 1$, $j = k + m - 2, \cdots, j = k + 1$.
Поэтому можно пересадить зрителя $j$ налево, потом еще раз налево и т. д., пока он не поменяется местами со зрителем $n$. В результате билетеру удастся пересадить зрителя $n$ на одно место правее, причем все зрители слева от $n$ сидят на чужих местах. Билетер может повторять эту процедуру до тех пор, пока не произойдет одно из двух: зритель $n$ окажется на своем месте или встретится второй случай ($k + m = n$).
Во втором случае билетер может рассадить по своим местам зрителей $k, k +1, \cdots, n$, пересаживая зрителя $n$ вправо до его места.
Таким образом, несколько зрителей в правом конце ряда будут сидеть на своих местах, а остальные - нет. Мы свели задачу к исходной с меньшим числом зрителей.
Ответ: Всегда.
