Question

5. For example the books at a library can be rearranged in arbitrary order by just swapping the locations of two books at a time. E.g. if we start with books in order (1 2 3 4) to get to (4 3 2 1) it is enough to swap (1 4), to get (4 2 3 1), and then (2 3) to get (4 3 2 1). Argue that it is always possible to rearrange the books in an arbitrary order even if we're only swapping adjacent books on the shelves. (So even library patrons that only mess up books close to each other can mess up the whole library, eventually.) The argument should be clear, and constructive, in the sense that you describe how this reordering can actually be done. Illustrate your argument by showing how to turn the order (1 2 3 4 5) into the order (4 1 5 3 2) by swapping only adjacent elements.

Answer 1