Proving Between the Lines

BLOG: Heidelberg Laureate Forum

Laureates of mathematics and computer science meet the next generation
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?

A large grid of dots, with three sets of dots that each lie on a straight line (horizontal, and two different diagonals) highlighted. The dots are not necessarily all next to each other on the 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.

A dot
A two-by-two grid of dots

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.

Two four-by-four grids, each with eight dots highlighted. One has four pairs of horizontally adjacent dots, alternating at different ends of the line, and the other has the eight 'edge' dots that aren't corners highlighted.

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.

A five-by-five grid of dots, with the last dot on the top row, the middle dot on the second row and the first dot on the third row highlighted, and a line drawn through

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.

A 52x52 grid with 104 spaces highlighted in black. The pattern has rotational symmetry.

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.

Avatar photo

Posted by

is a mathematician based in Manchester, who gives talks and workshops on different areas of maths. She finished her PhD in 2011, and since then has talked about maths in schools, at science festivals, on BBC radio, at music festivals, as part of theatre shows and on the internet. Katie writes blog posts and editorials for The Aperiodical, a semi-regular maths news site.

1 comment

Leave a Reply

E-Mail-Benachrichtigung bei weiteren Kommentaren.
-- Auch möglich: Abo ohne Kommentar. +