Question

2007 чоловік вишикувалися у шеренгу. Чи завжди можна розмістити їх по зросту, якщо дозволяється переставляти будь – яких двох людей, що стоять тільки через одного.

Answer 1

Ні, не завжди можна розмістити їх по зростанню, використовуючи тільки перестановки пари сусідів. Це пов'язано з тим, що загальне число перестановок обмежена і не завжди може відповідати всім можливим варіантам ростов.

Давайте розглянемо приклад. Уявімо, що у нас є 3 людини з різними зростами: A, B і C. вони збудовані в наступному порядку: A < B < C.

Ми можемо зробити перестановку B і C, і отримаємо такий порядок: a < c < B. Однак, ми не можемо переставити A і b тільки з використанням перестановок пари сусідів.

Таким чином, не завжди можливо розмістити 2007 чоловік по зростанню з використанням тільки таких перестановок.