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?
$\begingroup$
$\endgroup$
1
asked Feb 6, 2021 at 12:21
-
1$\begingroup$ I didn't come up with this problem. I will post a link later. $\endgroup$– Dmitry KamenetskyFeb 6, 2021 at 13:34
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
9
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:
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.
answered Feb 6, 2021 at 13:35
-
$\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$ Feb 6, 2021 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$ Feb 6, 2021 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$ Feb 6, 2021 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$– musefanFeb 8, 2021 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$ Feb 8, 2021 at 12:14
$\begingroup$
$\endgroup$
1
I hope this is the solution (I will work for the Bonus Part) :-
$\begingroup$
$\endgroup$
1
Alternate solution to @Anonymous' correct solution:
The gray dots represent the 10 dots. This also proves the bonus question of being able to solve it in different ways (non-mirror)
