# 8x8 Grid with no parallels

In the 8x8 grid graph shown below;

you can put points to the edge of grid as shown below (blue dots).

The example above has 4 points and you construct a line between two points as shown below;

so the question is

What is the maximum number of points you can have in an 8x8 grid graph, where no pairs of distinct points can create two parallel lines?

Note that one point cannot be used more than once while creating a new line and 4 points in a line is counted as parallel as well.

If this question was asked for 2x2, the answer would be 5:

• Do $4$ points in a line count as two parallel lines? May 16, 2022 at 4:16
• @RobPratt yes :)
– Oray
May 16, 2022 at 12:38
• I don´t understand where are those 5 lines in the 2x2 grid, If I don't count the perpendicular lines I count 4 no parallel lines, if I count the perpendicular lines I count 6 no parallel lines, can you show where are those 5 lines? May 16, 2022 at 13:58
• @stramin it is not the lines you need to count, it is points.
– Oray
May 16, 2022 at 14:06

I'm using a $$9 \times 9$$ matrix, with $$1$$ if there is a point and $$0$$ otherwise.

$$11$$ points:

0 0 0 0 0 0 0 1 0
0 1 1 0 0 0 0 0 1
0 0 0 0 0 0 0 1 0
0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1 0
0 0 0 0 1 0 0 0 0
1 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 1 0 0

• Let me guess - the solving method was "Integer Linear Programming" :) May 16, 2022 at 17:16
• @bobble I'd rather not say. :) May 16, 2022 at 18:22
• It seems the maximum number is $(n+2)$ for any $n\geq 3$? ($n$ is the number of points on the edge) Could you please check it?
– xd y
May 19, 2022 at 11:15
• @fljx showed that $n+2$ is an upper bound. It is attained for $n\in\{3,\dots,9\}$, but I don't know about larger $n$. May 19, 2022 at 17:15

It's fairly simple to prove an upper bound of:

11 points

Just look at how many points are in each row.

- If any two rows contain two (or more) points. You have two horizontal lines. So at most one row can have more than one point.
- If any row contains four (or more) points. You have two horizontal lines. So one row can have at most three points.

For a maximum of 8+3 = 11 points.

And @RobPratt has provided a solution with 11 points.

## Disclaimer

I misread the question and thought it said that I have to pick the max number of lines. I'm just leaving this up here in case it helps anyone

I got to

37 lines

Photo:

It may be possible to get this higher, but not by much as the upper bound is

40 lines cuz 81 pts/2(pts/line) = 40.5 lines

• The question seems to be about placing the points, and letting an adversary draw the lines. Or at least that's how I read it.
– Bass
May 16, 2022 at 3:37
• @Bass That wasn't stated in the post.
– JLee
May 16, 2022 at 9:00
• It says "no pairs of distinct points can create two parallel lines". For example A&B and R&T in your attempt can create parallel lines. May 16, 2022 at 9:22
• @Bass It appears that I misread the question. Thanks for pointing this out. May 16, 2022 at 19:18