10
$\begingroup$

You are given a 4x4 square grid. It has 16 cells and 25 grid intersections. Can you place 10 points at grid intersections, such that no three points lie on the same straight line? Lines can be oriented in any direction. Bonus question: can you find multiple solutions that are not rotations/reflections of each other?

$\endgroup$
1
  • 1
    $\begingroup$ I didn't come up with this problem. I will post a link later. $\endgroup$ – Dmitry Kamenetsky Feb 6 at 13:34
8
$\begingroup$

The answer to both main and bonus question is given by the following fact:

there are exactly five solutions, truly distinct even after rotations and reflections.

As follows:

grid1 grid2 grid3 grid4 grid5

This is the $n=5$ case of the no-three-in-a-line problem (link contains spoilers, obviously). In general, one might ask whether it's always possible to get $2n$ dots on an $n\times n$ grid (the theoretical maximum is $2n$, since each row and column can contain at most 2 dots). The answer to this question for general $n$ is unknown. The number of possible solutions, distinct even after rotations and reflections, is given by this OEIS sequence (again, link contains spoilers).

I'm not sure if there's a short and neat way to prove that this problem has exactly five solutions and no more, but it's been done by a direct case-bashing approach by Alberto Cid on Quora. Certainly it's easily verified that all five of the solutions shown above do work.

Interestingly,

just two of the five solutions (the first and last ones, according to the order I've put them in above) have any nice symmetry properties.

$\endgroup$
9
  • $\begingroup$ Correct and well done! This is a well known problem indeed. Even Erdos worked on it. It is still unknown whether 47x47 can be done with 2n points. The largest grid that can be done with 2n points is 52x52. $\endgroup$ – Dmitry Kamenetsky Feb 6 at 13:40
  • 1
    $\begingroup$ @DmitryKamenetsky Problems like this are so fascinating, when the answer is known only up to a finite point and then you've got a (still relatively small compared with some numbers in maths) 47x47 problem where it's not even known if a solution exists. I've never done combinatorics as a researcher, or even taken a formal course in it, but I can't deny it gives rise to some really fun problems :-) $\endgroup$ – Rand al'Thor Feb 6 at 13:43
  • $\begingroup$ Couldn't agree more! In fact I got so interested by this problem that I decided to have a go at the 47x47 myself. Today I wrote a heuristic solver. It only managed to find 13x13 so far, but early days still. Searching for symmetric solutions should reduce the search space considerably. $\endgroup$ – Dmitry Kamenetsky Feb 6 at 13:46
  • $\begingroup$ I don't understand why you say there are exactly 5? The first one that instinctively can to my mind is not listed in your 5, so there is at least 6. $\endgroup$ – musefan Feb 8 at 10:51
  • $\begingroup$ @musefan It's been proved mathematically that there are exactly 5, so the one you found must be equivalent (rotation/reflection) to one of those I mentioned here. $\endgroup$ – Rand al'Thor Feb 8 at 12:14
9
$\begingroup$

I hope this is the solution (I will work for the Bonus Part) :-

$\endgroup$
1
4
$\begingroup$

Alternate solution to @Anonymous' correct solution:

enter image description here

The gray dots represent the 10 dots. This also proves the bonus question of being able to solve it in different ways (non-mirror)

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.