4
$\begingroup$

In the 8x8 grid graph shown below;

enter image description here

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

enter image description here

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

enter image description here

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:

enter image description here

$\endgroup$
4
  • $\begingroup$ Do $4$ points in a line count as two parallel lines? $\endgroup$
    – RobPratt
    May 16, 2022 at 4:16
  • $\begingroup$ @RobPratt yes :) $\endgroup$
    – Oray
    May 16, 2022 at 12:38
  • $\begingroup$ 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? $\endgroup$
    – stramin
    May 16, 2022 at 13:58
  • 1
    $\begingroup$ @stramin it is not the lines you need to count, it is points. $\endgroup$
    – Oray
    May 16, 2022 at 14:06

3 Answers 3

4
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Let me guess - the solving method was "Integer Linear Programming" :) $\endgroup$
    – bobble
    May 16, 2022 at 17:16
  • $\begingroup$ @bobble I'd rather not say. :) $\endgroup$
    – RobPratt
    May 16, 2022 at 18:22
  • $\begingroup$ 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? $\endgroup$
    – xd y
    May 19, 2022 at 11:15
  • $\begingroup$ @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$. $\endgroup$
    – RobPratt
    May 19, 2022 at 17:15
4
$\begingroup$

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.

$\endgroup$
-1
$\begingroup$

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:

enter image description here

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

$\endgroup$
4
  • 6
    $\begingroup$ 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. $\endgroup$
    – Bass
    May 16, 2022 at 3:37
  • $\begingroup$ @Bass That wasn't stated in the post. $\endgroup$
    – JLee
    May 16, 2022 at 9:00
  • 4
    $\begingroup$ 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. $\endgroup$ May 16, 2022 at 9:22
  • $\begingroup$ @Bass It appears that I misread the question. Thanks for pointing this out. $\endgroup$
    – Ankit
    May 16, 2022 at 19:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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