100 человек выстроились в шеренгу. Всегда ли можно их расставить по росту, если разрешается переставлять любых двух людей, стоящих через одного?

Это метод сортировки. Он напоминает "сортировку пузырьком". Но таким способом отсортировать список или шеренгу нельзя, если не будет выгодных позиций. Что бы убедится в том что таким способом нельзя расставит 100 человек по росту возьмем пример из ряда чисел. Не будем использовать 100, нам хватит и 5-и. Запишем их в хаотическом порядке и попытаемся отсортировать:

3 1 5 2 4;

3 1 4 2 5;

4 1 3 2 5;

4 2 3 1 5.

Как можно видеть, цифра "1" не сможет стать на первое место, так же как и цифра "4". Так что таким способом построить шеренгу по росту нельзя.