Встроке записаны числа от 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], ' ');