MathDB

Freddy writes down numbers

1, 2,\ldots ,n

in some order. Then he makes a list of all pairs

(i, j)

such that

1\le i<j\le n

and the

i

-th number is bigger than the

j

-th number in his permutation. After that, Freddy repeats the following action while possible: choose a pair

(i, j)

from the current list, interchange the

i

-th and the

j

-th number in the current permutation, and delete

(i, j)

from the list. Prove that Freddy can choose pairs in such an order that, after the process finishes, the numbers in the permutation are in ascending order.

6

Problems(1)