mathschallenge.net

Problem

Using discs numbered 1 to 6, it is possible to place the discs in two bags, such that no bag contains its double in exactly four different ways:

If you had discs numbered 1 to 10, how many ways can you separate the discs into the two bags such that no bag contains its double?

Solution

If 1 is placed in one bag, 2 must be placed in the other bag. Now 4 must be placed in the first bag, and 8 must be placed in the second bag. Without loss of generality let us say that the first bag contains {1,4}, and the second bag contains {2,8}.

It is clear that 3 and 6 must be placed in separate bags, as must 5 and 10.

Regardless of how we arrange the other discs, 7 and 9 can be placed in either bag without any conflict. There are four ways we can arrange these two discs: {7} and {9}, {9} and {7}, {7,9} and {}, {} and {7,9}.

In the first bag we can have 3 and 5, 3 and 10, 6 and 5, or 6 and 10.

As each of these arrangements has four ways in which we can arrange 7 and 9, there are exactly 4 4 = 16 different ways in which we can fill the two bags such that no bag contains its double.

Investigate filling the bags with numbers 1 to n.