1 The Puzzle

On BlueSky, Sam Blatherwick posted a puzzle:

Ash, Blur, The Cure and Daft Punk decide to go on tour. They play $4$ different venues, Aberdeen, Belfast, Cardiff and Dorking.

Each night they rotate their venues, so Ash play in Aberdeen the first night and Belfast the next and so on… Daft Punk start in Dorking then go to Aberdeen and so on…

Prove it is impossible to see all the bands and all the venues in four nights.

What simple change would make it possible?

The last part, about find a scenario in which it works, is – of course – the most interesting. There are "easy" answers wherein it suffices to change the number of bands and venues (three and five both work) but there's also a more complicated answer which means that the original puzzle does have a solution if we change the words used to describe it.

And it's that bit which, for me, makes it worth writing down. Because that change of description is a mathematical trait. What we will do is redescribe the puzzle so that it is still the same puzzle but it allows a different generalisation to that from its original wording.

This is a very common mathematical habit.

A context may allow for many different descriptions that are equivalent for that original context, but which generalise in different ways. Sometimes there might be one which feels more "right" – and which may well have not been the original one – but most often each of these generalisations proves an interesting avenue of mathematical exploration. And part of that exploration will involve how the different generalisations interact and differ.

2 The Simple Solution

Let's start with solving the given puzzle. We can abbreviate everything to a single letter with uppercase for the bands and lowercase for the venues. So 'Aa' denotes band 'A' playing at venue 'a'.

Then on the first night, the available gigs are: Aa, Bb, Cc, Dd. On the second, they are Ab, Bc, Cd, Da. And so on.

We can illustrate the full round in a grid as in Figure 1.

Suppose we go to hear band 'A' on the first night1, so go to venue 'a'. Then all entries with 'A' or 'a' are no longer available for other nights. This removes 'Ab' and 'Da' from the second night, meaning we have 'Bc' or 'Cd' available. On the third night we already have 'Ac' and 'Ca' unavailable (from the first night), then regardless of which of 'Bc' or 'Cd' we chose on the second night, 'Bd' is unavailable on the third night leaving just 'Db' available. Finally, on the fourth night then 'Ad' and 'Ba' are unavailable from the first night, and 'Cb' and 'Dc' are unavailable from the third night.

What I find most intriguing about this argument is that the fact that we can't find somewhere to go on the last night doesn't depend on what happened on the second night. Either choice on the second leads to the same path through the rest of the puzzle. It's as if the freedom to choose on the second night is balanced by the inability to choose on the fourth.

We can illustrate the argument graphically by crossing off ineligible entries. After the first night, we cross off all entries with an 'A' or 'a'. We can also cross off all other entries from the first night.

For the sake of definiteness, let's suppose we pick 'Cd' on the second night, then we cross off all with a 'C' and 'd'

And then after the third night, where we had to pick 'Db', the state of play is as in Figure 4.

The key observation here is that each choice of a gig to attend crosses out a number of choices along three lines: a horizontal line representing the other gigs taking place that night, a vertical line representing the other gigs with that band, and a diagonal line representing the other gigs at that venue. But note that this diagonal line can "wrap round" if necessary. It's most obvious on the third night where the line for venue 'b' goes 'Db', 'Cb', and then wraps round to 'Bb' and then 'Ab'2.

So in the grid, all four gigs are crossed off on the last line and so no solution is possible.

3 Seeing Dobble

The grid with the lines is very reminiscent of how one describes the game of Dobble mathematically. I've done so in my post Fields and Games, and numerous others have written similar posts and articles.

Is that just a vague similarity, or is there something more going on?

Obviously the latter, otherwise I wouldn't have mentioned it!

So let's try a proof by Dobble. We're going to go for a generalisation of this puzzle in which there are $k$ bands, venues, and nights and we wish to see every band but never visiting the same venue twice (and only one gig per night).

There's one aspect of the puzzle that I'm going to relax, and that is that the bands have a particular order around the venues. So this puzzle is asking if there is some way to arrange the gigs so that someone can see each band according to the constraints, but not necessarily that the bands follow each other around. We'll come back to that later.

The other thing to make plain is that this is all about proving something is possible and not showing that it isn't. So this is a demonstration of how to arrange matters so that it works, under certain circumstances. If those circumstances fail then it doesn't mean that there isn't a way to make it work – just that this method can't be used.

With that in play, let's see how it works!

We need a Dobble pack with $k+1$ symbols per card. In the Fields and Games post I introduced the notion of a reduced pack, which means that there's no redundancy in the symbols. I'll assume this holds for this pack.

Now, we pick a base card. Let's suppose for a concrete example that $k=3$, so we have four symbols per card and on this base card the symbols are $♣$, $♢$, $♡$, and $♠$.

The next step is to divide the pack into piles according to which symbol they have in common with this base card. So we have a pile of cards with a $♣$ on it, a pile with a $♢$, and so on. As the pack is reduced, each of these piles must have at least one card in it. As explained in Fields and Games, the most each pile can have in it is $3$ cards. Indeed, here is a complete Dobble pack with four symbols per card:

Complete Dobble sets only exist for certain numbers of symbols per card, but we don't need that. What we need for this to work is that three of the piles have the maximum number of cards and that there is one more card (other than the base card). The "three" here has nothing to do with our choice of $k$ being $3$. This three relates to the fact that each gig has three attributes: band, venue, and night.

Indeed, what we do now is associate each of these piles with one of those attributes. So, for example, the three cards with $♣$ on them correspond to the three bands, with $♢$ to the venues, and with $♡$ to the nights. The exact correspondences don't matter, but we need to fix them.

Choosing a symbol then chooses one card from each of the $♣$, $♢$, and $♡$ piles and thus picks a band, a venue, and a night. For example, the cards that share the symbol $a$ are:

Finally, taking a card from the $♠$ pile gives a set of gigs for a person to attend who wants to see each band, each venue, but only go to one gig per night. This is because that card shares a symbol with each card in the $♣$ pile, so each band is seen. It shares a symbol with each card in the $♢$ pile, so each venue is visited. And it shares a symbol with each card in the $♡$ pile, so each gig is on a different night.

And if there are more cards in the $♠$ pile then more people can achieve this aim, with the additional fact that no two of them will ever attend the same gig!

4 The Truth is in the Cards

For this to work, we don't need a complete Dobble pack. But if we do then something a bit special happens. The remark at the end of the previous section, that we can have more people attending, extends further.

Let's take $k=5$, so we have six symbols per card and note that there is a complete Dobble pack with this many symbols per card. Then when we split the pack according to the symbol in common with the base card we have six piles and each pile has five cards in it.

As before, we can identify the cards in the first pile with the bands, the second with the venues, and the third with the nights. The fourth can be a group of five friends who between them want to go to every gig but never want to go together.

That leaves two more piles that can be two more attributes. It may be that these friends want to have new outfits for the gigs, but given how many they are going to can only afford one outfit each. So they agree to swap them around (hopefully with a visit to the launderette between each night!). But, of course, it would be awful if the same outfit were seen at the same venue, or by the same band. If that were to happen then, to coin a phrase, the gig would be up. So we assign the cards in another pile to the outfits.

Lastly we could have mode of transport to the gig. These can be the cards in the sixth pile.

There are now $5\times 5=25$ symbols on the cards apart from the symbols on the base card. Each symbol is on one and only one card from each pile, so each symbol corresponds to an event consisting of a person wearing an outfit travelling a particular way to a venue to see a band on a particular night. Everyone sees every band, visits every venue, wears every outfit, and travels in every way.

And there are no clashes.

So next time you want to organise a series of nights out, reach for the Dobble set.

5 Primal Scream

There's a couple of loose ends to tie up here.

One is related to the fact that we don't need a full Dobble deck if we're just interested in bands, venues, and nights. So the conditions that guarantee a full Dobble set aren't needed. It turns out that there is a method to get a solution if $k$ is odd.

The other is that a full Dobble set is possible if $k$ is a prime power. Now, there's other issues with $2$ that rule it out3 but $4=2^2$ is famously a prime power so there should be a solution with $4$.

So the Dobble solution gives us both more and fewer solutions than it should.

Which is a bit odd.

6 Playing the Odds

We don't need a full Dobble deck, we just needed that when we split the pack using a base card then there were three full piles and one extra card.

It turns out that there's no problem with the three full piles. The difficulty is the extra card. Let's see how to make a pack with the three full piles. We start with a $k\times k$ grid of dots, as in Figure 5, wherein each dot represents a distinct symbol.

Remember that we also have a base card with a separate set of $k+1$ symbols on it.

We pick one of the symbols on the base card, and then for every row in the grid we create a card with the symbols from that row together with our chosen symbol from the base card.

Then we do the same with the columns and a different base symbol.

And finally, we do the same with the lines parallel to the leading diagonal (viewed as going from bottom left to top right). In this case, we allow for wrap-around so that when a line goes off the side of the grid then it comes back on at the opposite side.

This produces three piles, each of which has $k$ cards in it, and these cards satisfy the Dobble requirements. Cards in the same family share the base symbol. Cards in different families share a single symbol which is where their two corresponding lines cross.

The difficulty now is to find a card in a fourth pile.

Here's some arithmetic. We can give each of our lines an equation, but because we allow the lines to wrap-around then we're actually working in modular arithmetic, with modulus $k$, and our equations have to be interpreted in this arithmetic.

The cards in the first pile all have equations of the form $y=c$, with $c$ one of $0$ to $k-1$. The cards in the second are $x=c$. And the cards in the third are $y=x+c$.

What we need to find now is a fourth type of line. We can assume that it is of the form $y=mx$4, with $m$ between $0$ and $k-1$.

We need it to intersect with every other line once and once only, so in particular, it can't be one of the previous lines. Therefore, we can't have $m=0$ or $m=1$.

It will intersect $x=c$ uniquely at $(c,mc)$ so the vertical lines are sorted. To intersect $y=c$, we need to find $x$ such that $mx=c$ and we want there to be only one solution to this. To intersect $y=x+c$, we need to find $x$ such that $mx=x+c$ and we want there to be only one solution to this.

If we were working over the reals, we would have $x=\frac{c}{m}$ in the first and $x=\frac{c}{m-1}$ in the second. But we aren't working over the reals, we're working in modular arithmetic. And in modular arithmetic, multiplication isn't always invertible. The condition required is that the number we multiply by be coprime to the modulus. So we need both $m$ and $m-1$ to be coprime to $k$.

If $k$ is odd then $m=2$ will do.

If $k$ is even, then as one of $m$ and $m-1$ is even, one of them will not be coprime to $k$.

Hence this method works if, and only if, $k$ is odd.

Again, this doesn't show that there isn't a solution if $k$ is even. Just that this method doesn't produce it.

Also worth noting that because the lines for the nights are parallel lines in the grid, the solution produced by this method does satisfy the requirement of the original puzzle that the bands follow each other around the venues.

7 The Universe Nextdoor

Let's return to the solution that isn't a solution. There's a Dobble pack with $5$ symbols per card that achieves the maximum size because $5-1=4=2^2$ is a prime power. So there should be a solution to the puzzle with four bands.

But there isn't.

The resolution of this contradiction is that the Dobble framing of the puzzle loses one key component of the original puzzle, namely that the bands and venues follow a particular order. The Dobble solution to the four band puzzle does not have this.

However, we can redescribe the original puzzle in such a way that the Dobble solution does fit. For this, we have to explain how the bands know which venues they will play at. Let's suppose that band 'A' picks their venues and labels them in order $0$, $1$, $2$, and $3$. They then tell the other bands their first venues, so 'B' is at $1$, 'C' is at $2$, and 'D' is at $3$.

To figure out where to go on a given night, each band could just add $1$ to their previous location (with wrap-around, so that $3+1$ wraps to $0$). But they could be more ingenious. What they could do is to ask 'A' where they are playing that day, and then add their original venue's number to that. So on the last night, 'A' is playing at $3$ and so 'D' plays at $3+3=6\equiv 2mod4$.

With the labels as $0$, $1$, $2$, and $3$ and addition defined in the usual way (modulo $4$) then we get exactly the same behaviour as in the original puzzle: the bands cycle round the venues.

Now let's suppose that 'A' is a bit more adventurous. They label the venues $0$, $1$, $\alpha$, and $1+\alpha$ and tell the other bands their venues in that order. The difference now is that addition works a bit differently. As is implied, adding $1$ and $\alpha$ results in $1+\alpha$, and $0$ behaves as one would expect. But $1+1$ and $\alpha +\alpha$ both equal $0$. Now, when 'A' is playing at $1+\alpha$ on the last night then 'D' plays at $1+\alpha +1+\alpha =0$. In full, the gigs are as in Figure 6.

With this arrangement, an order to attend gigs is to see 'A' in venue $0$, then 'D' in $\alpha$, 'B' in $1+\alpha$, and finally 'C' in $1$. When drawn on the grid, this doesn't look like a straight line, but it is as it has equation5 $y=(1+\alpha )x$.

So if we change the description of how the bands decide on their venues, we can vary the universe in which the whole scenario takes place. In one universe is the original puzzle which warrants no solution. But in another universe, with this strange rule for addition, the puzzle admits a solution.

And that's a common mathematical strategy. Don't like the problem? Try the universe nextdoor, it might just have a solution there.