Arrange $n$ points in the plane such that such that the number of lines pass through exactly $\sqrt{n}$ will be maximized.

78 Views Asked by At

Given a number $n$ which is a perfect square, define a set of $n$ points in the plane, such that the number of lines passing through exactly $\sqrt{n}$ points will be maximized.

My idea:

Arrange the points as a square lattice, then you will have $2\sqrt{n} + 2$ lines pass thru $\sqrt{n}$ points (Two diagonals, $\sqrt{n}$ horizonal and $\sqrt{n}$ vertical).

enter image description here

I was thinking about induction, But was not able to go further.

I need some assistance to prove that In order to achieve the maximum, the points must be arranged as a square lattice, I've been sitting on it for a while now.