There are several ways to do this problem. We liked this one sent in by Charlotte, Y11.

We can assign each person a number. Even though order doesn't matter we can use this to see how the people are paired up, eg here are the "best friends".

1 2 3 4 5 6 7 8

Only the first three pairings matter as the fourth will be determined by the previous ones.

The first pairing (with person 1) has 6 possibilities (everyone except the X):

1 X 3 4 5 6 7 8

The second pairing (with person 2) has 5 possibilities: (8 people, subtract themselves and the two people in the first pairing). In this example 1 has been paired with 3.

X 2 X 4 5 6 7 8

Now say that 2 had been paired with 4. Number 5 would have two options, 7 or 8:

X X X X 5 X 7 8

If 2 had instead been paired with a "best friend" had not been paired, the next number would still have two choices as the last two friends (7 and 8 in this instance) cannot be left together.

In this example 2 paired with 5 (it could just as well be 6 , 7 or 8), meaning that 4 could not pair with 6 as thi swould leave 7 with 8. So again the third person to be paired has two options.

X X X 4 X X 7 8

Overall the number of options are

First pair: 6

Second pair: 5

Third pair: 2

Therefore the number of possibilities should be 6 x 5 x 2 = 60

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

Perhaps the easiest alternative method is just to work through all the possibilities, using symmetry to reduce the number of options where possible. One way to visualise this is using a tree diagram – you may want to draw out your own.

Let’s call the students A, B, C, D, E, F, G, H, and say that the best friend pairs are AB, CD, EF and GH.

To start with, A can be paired with any of the six students C, D, E, F, G or H. These options are all fully symmetric (we could always just relabel the students if necessary), so we can assume that A is paired with C and multiply whatever answer we get by six.

Next, let’s think about who we can pair B with. There are essentially two cases here. Note that these cases are not symmetric, because we have some special information about D – namely that D’s best friend is paired with A.

Case 1: B is paired with D. It is then easy to see there are two possible pairings for EFGH: EG and FH or EH and FG.

Case 2: B is paired with one of the four students E, F, G, H. These are all symmetric, so we can assume B is paired with E and multiply however many possibilities by 4.

Since G and H cannot be in a pair, we have 2 choices of partner for G (which are D and F), and both options fully determine a valid set of pairings.

Thus Case 1 gives a total of 2 possibilities, while Case 2 gives 8. Adding these together and multiplying by 6 for the initial choice of A’s partner, we find that there in total there are 60 productive pairings Mrs Green could choose.

Another way to do this is to use a variant of the inclusion-exclusion principle (you can look this up if you haven’t heard of it before). This is a bit more tedious for 8 students, but if Mrs Green’s class got any bigger then this would quickly become the more efficient strategy. What we will describe below isn’t exactly the inclusion-exclusion principle, but it follows a similar idea.

How many pairings are there in total, if we forget about the “best friends” restrictions? We have a total of 7 choices for who to pair the first person with, then 5 choices for the next person to be paired and so on, giving a total of 1 x 3 x 5 x 7 = 105 possibilities.

How many pairings contain exactly 4 pairs of best friends? This is easy, there is exactly 1.

How many pairings contain exactly 3 pairs of best friends? Clearly 0, as if a pairing contains 3 pairs of best friends then the fourth pair of best friends must also be partnered.

How many pairings contain exactly 2 pairs of best friends? Let’s start by counting the number of pairings that contain exactly the best friend pairs AB and CD, and then use symmetry to multiply by 6 (the number of choices of two best-friend pairs) and finish the job. It is easy to see there are 2 such pairings. Therefore, we have 12 pairings containing exactly two best friend pairs.

How many pairings contain exactly one pair of best friends? Again, we will assume this pair is AB and multiply by 4 at the end. Now there are 1 x 3 x 5 = 15 possible ways to pair the remaining six students, of which 1 contains all four best friend pairs, 2 also contain only CD, 2 also contain only EF and 2 also contain only GH. Therefore 15 – 1 – 2 – 2 – 2 = 8 contain just AB. Multiplying this by 4 gives 32 pairings containing exactly one of pair of best friends.

Finally, we subtract these “bad pairings” from the total number of pairings, which was 105. This gives 105 – 1 – 12 – 32 = 60, which (reassuringly) is the same answer we got from the other method.

Challenge 251: Chatty Classmates