Question

There are six friends in a book club and each of them gives their book to one friend and receives a book from another friend. How many different ways can the books be exchanged, assuming that no two friends can exchange (give and receive) books?

Answer 1

`160`

Explanation:

We can represent the exchanging of the books by a directed graph with `6` nodes representing the friends and arrows between them representing the direction in which books go.

If they all exchange books at once, then every node has an arrow going from it and one going to it.

Since there are a finite number of friends, the arrows must form cycles.

From the conditions of the question, there are no `1` or `2`-cycles.

Hence the only possible simultaneous exchanges fall into two categories:

• One `6`-cycle.

• Two `3`-cycles.

Consider each case in turn:

Case: One `6`-cycle

• The first friend has `5` possible friends to choose.

• The friend to whom the book is given has `4` possible choices.

• The next friend has `3` possible choices.

• The next friend has `2` possible choices.

• The next friend has `1` possible choice.

• This last friend gives their book to the first friend.

So there are `5! = 120` possible choices of a single `6`-cycle.

Case: Two `3`-cycles

• The first friend has `5` possible friends to choose.

• The friend to whom the book is given has `4` possible choices.

• The next friend has just one choice - to give their book to the first friend.

• The first of the `3` remaining friends has `2` choices.

• The next friend has `1` choice, to give their book to the last remaining friend.

• The last friend gives their book to the first friend of their `3`-cycle.

So there are `5 * 4 * 2 = 40` possible choices of two `3`-cycles.