В строке записаны числа от 1 до 2015 в случайном порядке. Разрешается менять местами любые числа, стоящие через 1, либо через 2. Докажите, что можно расставить числа по возрастанию.

Просто запускаешь механизм "пузырьковой" сортировки:

const n=2015

var

a:array[1 ... n] of integer;

i, j, d: integer;

begin

(считаем, что массив у нас уже заполнен, так что перехожу сразу к части с сортировкой)

for j:=n downto 2 do

for i:=1 to (j-1) do

if a[i]>a[i+1] then

begin

d:=a[i];

a[i]:=a[i+1];

a[i+1]:=d;

end;

end.

доказательства ради, можно вывести массив на печать, добавив перед последним "end" строки:

for i:=1 to n do

wirite (a[i], ' ') ;