# 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…)