исла I, 2, 3, ...., n розташовані в деякому порядку. Дозволяється міняти місцями будь-які два поруч стоять числа. Доведіть, що якщо проробити непарне число таких операцій, то напевно вийде відмінний від первісного розташування чисел 1, 2, 3, ..., n. p>
Рішення. Нехай a 1, a 2, ..., an - довільна перестановка з чисел 1, 2, 3, ..., п. Будемо говорити, що числа а i , і а j , утворюють в цій перестановці інверсію, якщо i < j , але ai > aj , тобто більшу з цих чисел передує меншого. Помінявши місцями два сусідніх числа в перестановці, ми збільшимо або зменшимо число інверсій на +1. Проробивши ж непарне число таких операцій, ми змінимо парність числа інверсій, а значить, змінимо і перестановку.
2.16. Доведіть, що затвердження завдання 2.15 залишиться справедливим, якщо дозволити міняти місцями будь-які два числа в перестановці. p> Вказівка.
Доведіть, що будь-які два числа можна поміняти місцями, проробивши непарне число раз операцію, описану в задачі 2.12. p> Перехід від однієї перестановки чисел 1, 2, 3, .... п до іншої перестановці цих чисел, при якому небудь два числа міняються місцями, а інші залишаються на місці, називається транспозицією. Результат завдання 2.16 можна сформулювати так: виконавши непарне число транспозицій, ми змінимо перестановку
2.17. У різних пунктах кільцевого автодрому в один і той же час в одному напрямку стартували 25 автомобілів. За правилами гонки автомобілі можуть обганяти один одного, але при цьому заборонений подвійний обгін. Автомобілі фінішували одночасно в тих же пунктах, що і стартували. Доведіть, що під час гонки було парне число обгонів.
Рішення.
забарвиться один з автомобілів у жовтий колір, а іншим автомобілям присвоїмо номери 1, 2, 3, ..., 24 у тому порядку, в якому вони розташовуються на старті за жовтим автомобілем. У центрі автодрому встановимо світлове табло, на якому після кожного обгону будемо вказувати номери автомобілів в тому порядку, в якому вони слідують за жовтим автомобілем. Тоді обгін, в якому не бере жовтий автомобіль, призводить до того, що на світловому табло міняються місцями два сусідніх числа.
Подивимося, що станеться, якщо який-небудь автомобіль обжене жовтий. Якщо перед цим обгоном числа на табло утворювали перестановку а1, А2, ..., А24 , то після обгону вони утворюють перестановку а2, а3, ..., А24, а1. Зауважимо, що до такої ж перестановці можна прийти, виконавши послідовно 23 транспозиції: а1, а2, а3, ..., А24 Г а2, а1, а3, ..., А24 Г а2, а3, а1, ..., А24 Г а2, а3, а1, ..., А24 Г ... Г а2, а3, ..., а1, А24 Г а2, а3, ..., А24, а1
Якщо ж жовтий автомобіль скоїв обгін, то з перестановки а1, А2, ..., А24 отримаємо перестановку А24, а1, а...
