linear algebra – Given a positive integer $n$, some straight lines and lattice ponts such… Prove that the number of the lines is at least $n(n


Given a positive integer $n$ and some straight lines in the plane
such that none of the lines passes through $(0,0)$, and every lattice point
$(a,b)$, where $ 0leq a,bleq n$ are integers and $a+b>0$, is contained
by at least $a+b+1$ of the lines. Prove that the number of the lines is at
least $n(n+3)$.

Solution?

  • Say we have $l$ lines and each can pass at most $n+1$ points. Say $k$ of them pass through $n+1$ points, then $kleq 2n$. So all of them pass at most through $$k(n+1)+n(l-k) leq (l+2)n$$ points.
  • On the other hand all points pass thorugh at least $$sum_{a=0}^nsum_{b=0}^n (a+b+1)-1 = n^3+3n^2+3n $$ lines.
  • So we have $$n^3+3n^2+3nleq (l+2)nimplies lgeq n(n+3)+1$$
    and thus a conclusion.

Now, I wonder if there is some linear algebra aproach to this problem? (Like defining some polynomials which wanish on some set of point…)