Earlier today I asked you the following problem about a hexagonal grid similar to the one that was used in Blockbusters, a student quiz show from the 1980s and 1990s.
The grid is also a model of the mathematical theory of percolation – but more of that later.
The grid below shows a 10×10 hexagonal tiling of a rhombus (i.e. a diamond shape), plus an outer row that demarcates the boundary of the rhombus. The boundary row on the top right and the bottom left are coloured blue, while the boundary row on the top left and the bottom right are white.
If we colour each hexagon in the rhombus either blue or white, one of two things can happen. Either there is a path of blue hexagons that connects the blue boundaries, such as here:
Or there is no path of blue hexagons that connects the blue boundaries, such as here:
There are 100 hexagons in the rhombus. Since each of these hexagons can be either white or blue, the total number of possible configurations of white and blue hexagons in the rhombus is 2 x 2 x … x 2 one hundred times, or 2100, which is about 1,000,000,000,000,000,000,000,000,000,000.
In how many of these configurations is there a path of blue hexagons that connects the blue boundaries?
Solution Exactly 50 per cent.
The proof is based on the insight that if there is a path of blue hexagons between the blue boundaries, there is no path of white hexagons between the white boundaries. And if there is no path of blue hexagons between the blue boundaries, then there is a path of white hexagons between the white boundaries.
This insight is what made Blockbusters work as a game: contestants either had to create a path from the top to the bottom, or from the left to the right, by answering the questions correctly. It was impossible for there to be a left-right path and a top-bottom path, or for there to be no path at all, which meant that it was guaranteed that only one side would win.
Yet the insight is not quite enough. You also need to prove that on exactly half of all possible configurations, there is a blue path. Here’s one way to do it. Let’s start with some configuration, such as this one below. It has a blue path joining the blue boundaries, and no white path joining the white boundaries.
Let’s now change all blues to whites and all whites to blues.
And finally let’s flip it, so the top left becomes bottom left, and top right becomes bottom right:
In other words, we started with a configuration in which there was a blue path connecting the blue boundaries, and we turned it into a configuration in which there was no blue path connecting blue boundaries. And if we were to repeat this procedure (swap colours, then flip) we get back to the original configuration.
Alternatively, just say we started with a configuration with no blue path connecting the blue boundaries. That would mean that there was a white path between white boundaries. If we performed the “swap colours, then flip” procedure we would create a configuration in which there was a blue path connecting blue boundaries. And by repeating the process we would get back to where we started.
We conclude, therefore, that whatever configuration of the rhombus we choose, this configuration is part of a pair: one that has a blue path between blue boundaries, and one that has a white path between white boundaries.
(As mentioned above, it is impossible for the same configuration to have both a blue path between blue boundaries and a white path between white boundaries.)
If the configurations come in pairs, the number of configurations with a blue path between blue boundaries must equal the number of total configurations that don’t, hence the number with a blue path is 50 per cent. Ta-dah.
Now, what has this got to do with the smell of coffee?
As I mentioned in the original story, percolation is a mathematical area that is concerned with how fluids flow through porous materials. French mathematician Hugo Duminil-Copin won the Fields Medal, maths’ most high profile prize, earlier this month for his work on this area.
The hexagonal grid is a model of a material, and each blue cell represents, say, the presence of a gap for a liquid to percolate through. Percolation theorists are interested in questions such as what percentage of the total number of possible configurations of the grid has blue paths?
As the puzzle showed, when the probability that a hexagon is blue or white is 50/50, then half of all configurations have paths. But what happens when we change the probability that a hexagon is blue to less, or more, than 50 per cent? And what about introducing more than two possible states for each hexagon? The answers to these questions have helped scientists understand the behaviour of phase-transitions – when one underlying structure suddenly becomes another one – which has had applications in physics, biology, ecology and network theory.
I hope you enjoyed this puzzle. I’ll be back in two weeks.
Thanks to Ariel Yadin, of Ben-Gurion University in Israel, for suggesting this puzzle.
I set a puzzle here every two weeks on a Monday. I’m always on the look-out for great puzzles. If you would like to suggest one, email me.