Депутаты за круглым столом

[Ktina]

Для 120 депутатов приготовили круглый стол, разложив по его краю листочки с фамилиями этих депутатов (однофамильцев среди них нет). После того, как депутаты уселись, оказалось, что каждый из них сидит против листочка с чужой фамилией. Наша задача повернуть стол так, чтобы как можно большее число депутатов оказалось против своих фамилий. Какого наибольшего числа мы можем гарантированно добиться?

[NSKuber]

Ответ: $2$.
Так как при начальном положении никто не сидит против своей фамилии, положений стола 120, и для каждого из 120 депутатов существует положение, при котором он находится против своей фамилии, по принципу Дирихле существует положение, при котором более одного депутата сидят правильно.
Построение, при котором больше двух нельзя: выберем первого депутата, занумеруем от него по часовой стрелке депутатов $1,2,3,\ldots,120$, а на соответствующих листочках напишем фамилии $120,119,\ldots,2,1$. Тогда при любом положении стола, если напротив депутата $x$ лежит листок $y$, то напротив депутата $x+k$ лежит листок $y-k$, $k=1,\ldots,119$ (всё по модулю $120$). Если в каком-то положении стола для депутата $x$ и его листочка $y$ выполнено $x=y$, то $x+k=y-k \mod 120$ выполняется только для $k=60$. То есть при таком раскладе всегда либо $0$, либо $2$ депутата сидят где надо.

[Ktina]

NSKuber
Спасибо за исчерпывающее решение.