Перестановки чисел по кругу — задача по олимпиадной математике Алексее
По кругу выписано несколько чисел. Если для некоторых четырёх идущих подряд чисел a, b, c, d произведение чисел a – d и b – c отрицательно, то числа b и c можно поменять местами. Докажите, что такие операции можно проделать лишь конечное число раз.
Разобрать решение
Рассмотрим сумму P попарных произведений соседних чисел. Заметим, что при наших операциях P увеличивается. Действительно, при допустимой перестановке слагаемые ab и cd заменяются на ac и bd, а остальные слагаемые остаются прежними (bc превращается в cb). Раскрыв скобки в указанном в условии неравенстве, получим ab + cd – ac – bd < 0, то есть ab + cd < ac + bd.
Но, поскольку всевозможных расстановок данных чисел по окружности конечное число, величина P может принимать только конечное число значений. Таким образом, когда-нибудь увеличение полуинварианта P прекратится, а это значит, что не будет возможности провести разрешённую операцию.
Обсуждение
0Комментариев пока нет.