Sam’s dad is in a mathematical conundrum – so she’s asked Katie, one of our editors, if maths can save the day.

Dear The Aperiodical,

My dad is going away on a golfing holiday with seven of his friends and, since I know a little bit about mathematics, he’s asked me to help him work out the best way to arrange the teams for the week. I’ve tried to work out a solution, but can’t seem to find one that fits.

They’ll be playing 5 games during the week, on 5 different days, and they’d like to split the group of 8 people into two teams of four each day. The problem is, they’d each like to play with each of their friends roughly the same amount – so each golfer should be on the same team as each other golfer at least twice, but no more than three times.

Can you help me figure it out?

Sam Coates, Manchester

Dear Sam

Thanks for getting in touch! This is actually quite a constrained problem, and it’s no wonder you’ve struggled to find an answer. I’ve looked into it, and here’s what I’ve found:

• Each day, we need to split the 8 golfers into two teams of four. There are $8 \choose 4$ different ways to do this – we’d choose four of the eight, and call that ‘team A’, and the other four would make ‘team B’. This gives 70 options, which we can divide by two (since if we chose players 1,2,3,4 that would give an equivalent team split as if we chose players 5,6,7,8, so we’ve counted each split twice) – giving 35 options.

• Next, we need to choose five of these splits to make the five consecutive days. It’s probably safe to assume that you’d like a different one for each day, so the number of possible ways to do this is $35 \choose 5$; if we choose (without loss of generality) to make the set on the first day 1234 vs 5678, we can reduce this to $34 \choose 4$ $ = 46,376$ different ways to arrange people for the week.

Surely this is loads of possibilities, and we’ll definitely be able to find one that fits the bill?

If we look at the constraints you’ve set, it turns out we don’t actually have a lot of options for this to work; if we have 8 players, playing for 5 days, that means our plan of the week will look like this:

Here, I’ve arranged it so that (without loss of generality) the first day is 1234 vs 5678, and then for each of the other days, the team which contains player 1 is Team A.

What we want is for each player to play with every other player two or three times. Looking at the grid, we can see that e.g. Player 1 plays with fifteen instances of a person; that is, the first three are 234, but the other 12 aren’t fixed yet. Each player similarly plays on a team with 15 other instances of a player. Of those 15, given there are 7 other players, we must have 6 lots of ‘the same player twice’ and one lot of ‘the same player three times’.

\[ 15 = (2 \times 6) + (1 \times 3) \]

That’s not a lot of choices – any combination where someone plays with two different people three times can immediately be rejected. Also, since ‘Player 1 plays on a team with Player 2 three times’ immediately implies ‘Player 2 plays with Player 1 three times’, the players have to pair off into four pairs of ‘triple buddies’, and every other pairing must happen exactly twice.

It’s quite possible to work out setups where e.g. Player 1’s requirements are satisfied; if we fill in the left hand half using two of each number between 2 and 7, we might get a setup like this:

Checking the number of times 2 pairs with each number quickly reveals that if we make our missing final entry on the left be a 2 (giving 3 4 5 7 on the right), then 2 pairs with everything except 1 twice, and 1 pair with everything except 2 twice, and then 1 and 2 are a pair of ‘triple buddies’.

However, this solution falls down as soon as you check 3, which only occurs once with 5. In fact, I’ve tried this several times with different starting points, and it never seems to get past satisfying 1 and 2, no matter how much I fiddle with it.

This was when I started to suspect this is an impossible task; the problem is so constrained that no set of combinations will satisfy it. In order to check, and since this is a nice finite question, we can write a computer program. In this case, I used group theory software called MAGMA, which is very used to handling sets of objects, and sets of sets of objects, and has lots of nice functions designed for this kind of problem.

Roughly, the steps the program took were:

• Generate the list of 35 possible left-hand sides
• From this, generate the list of 46,376 possible weeks of golf
• Take the set of pairs of numbers from the set $\{1,\ldots,8\}$
• For each possible golf week, determine how many times each pair occurs
• As you go through the list, if any set of days has pairs occurring only in multiples of 2 or 3, print it on the screen.

The program took a few seconds to run, since this kind of number-crunching is pretty easy if you’re a computer. When it had finished, the screen was sadly blank. (I didn’t write an extra line into the program to output a sad face if there were no matches, but we should have).

This means there’s no way to arrange eight people into five games of golf so everyone plays with each other 2 or 3 times. But, since this is one of those ‘real world problems’, I figured rather than come back to you with the answer “NO”, I’d come back with something your dad might find useful. I scanned the list again, this time looking for entries where everyone plays each other at least ONCE, but no more than three times.

There were plenty of results, although some of them had 6 or more pairs which only got one game together. I did find what I think is the most pleasing of all the possible solutions, which only has four ‘one-game pairs’, and if the 8 players were, for instance, four couples, or four pairs of friends, you could arrange it so they only play each other once. Here’s the solution:

The four ‘one-game pairs’ are $(12)$, $(34)$, $(56)$ and $(78)$, and the only time they get to play together is on day one (provided that’s the order you choose to put the days in). If you look at the left-hand column, this has a pleasing symmetry to it. The 3s and 4s in their column follow an ABBA pattern; the 5s and 6s go ABAB, and the 7s and 8s go AABB. I couldn’t have designed a more logical system myself, if it hadn’t been spat out at me by a simple computer program.

What would be nice is if we could find a more elegant proof that this isn’t possible (obviously, your dad won’t care, but we will feel better about it). There’s a branch of mathematics called Combinatorial Design Theory, which deals with ways to construct different sets of subsets of a set, given constraints like these. For example, a balanced block design is a way of picking a number of blocks, i.e. smaller sets, from a set of objects, so that each pair of objects occurs in the same number of blocks.

While I’m sure a design exists that’s able to answer this particular question, I don’t know enough about design theory to say for sure. Maybe one of our readers knows, and can comment below?

I hope this helps to answer your question, and I wish your dad a great golf week, with lots of small numbers in it!

Katie