Proving Between the Lines
BLOG: Heidelberg Laureate Forum
Unsolved puzzles, unproven conjectures, and open-ended questions are fascinating to mathematicians – both because they present the tantalising possibility of solution, and because they remind us about how much we don’t already know. Much of the maths people learn at school was completed hundreds of years ago – and it’s easy to forget just how close the frontiers of human knowledge can be.
One example I came across recently was a problem called the ‘no-three-in-line’ problem – a question from 2-dimensional geometry, regarding points and lines in a flat plane.
Given an n-by-n grid of equally spaced dots, can you pick 2n dots so that no three of the dots lie in a straight line?
Some disallowed sets of dots and the lines they lie on
Introduced in 1900, it has been called “one of the oldest and most extensively studied geometric questions concerning lattice points”, and it’s a simple enough problem to state, but actually leads to some unanswered questions.
This question is carefully stated – if our grid measures n by n, it would be impossible to place more than 2n dots without three of them lying in the same row or column, by the pigeonhole principle; once each row contains 2 dots, there’s nowhere else a third dot can be placed without placing three in that line. But given the restriction of 2n, can we find a solution? And, how many possible solutions are there?
It’s usually instructive to start with smaller examples and work our way up. The line limitation is always ‘no three in a line’, regardless of the size of grid, and the number of dots is 2n for an n-by-n grid. A 1-by-1 grid is outside of the bounds of this problem (mainly since it doesn’t contain 2n = 2 dots we could choose!) but a 2-by-2 grid is our basic trivial example – I can highlight all four dots, and I’ll never find three in a straight line.
Once I get to a 3-by-3 grid, there’s more of a proper challenge – we now have to avoid three in a horizontal or vertical line, or three on a 45-degree diagonal. There’s actually only one way to fit in 6 dots with these restrictions – up to rotation and reflection – and I won’t spoil the answer in case you want to work it out for yourself.
Expanding to a 4-by-4 grid, now trying to fit 8 dots, makes for more of a challenge. We still have to watch out for the 45-degree diagonals, and now there are three lines in each direction we can make such a diagonal on.
There are four different solutions to this (up to rotation and reflection); two are shown below.
As we increase the size of the grid further, the problem evolves. Once we get to a 5-by-5 grid on which we have to place 10 dots, we find another diagonal comes into play – the marked dots can form a straight line of three, so this is another possibility we need to exclude.
As the grid gets bigger, and the number of possible arrangements gets bigger very quickly, we find that more and more restrictions – more directions in which three dots can lie on a straight line – creep in, which makes the problem harder.
This suggests that if these additional diagonals become common enough, at some point, placing 2n points might no longer be possible. 2n points can be placed on an n-by-n grid with no three in a line for all n up to 46, and for n=48, 50 and 52.
Solution for n=52, the current record
For any size of grid, algorithms have developed that allow 1.5 × n points to be placed without making a line of three. But solutions that place 2n points haven’t been found for any larger n than 52, nor has anyone found a way to place 47, 49 or 51 points.
It’s conjectured that as n increases, the number of points it’s possible to place gets smaller – and the limit is conjectured to be π/√3 (about 1.8 × n). This remains conjecture, though, as nobody has managed to prove it, and the exact maximum number of points that can be placed for a given value of n is not known.
Even though at smaller scales this is a fun puzzle even children can play with, if you increase the parameters far enough it becomes an open problem in mathematics. The no-three-in-line problem has connections to questions in graph theory and discrete geometry, and solutions for this problem can be used in finding solutions to others, including the Heilbronn Triangle Problem.
It’s also nice to have challenges like this to test our computational and mathematical skills, and I hope mathematicians continue to tinker with unsolved problems – even if they seem unrelated or trivial – and push the boundaries of what we know about the universe.
sehr interessant danke!