Given a positive integer $n$ and some straight lines in the plane such that none of the lines passes through $(0,0)$, and such that every lattice point $(a,b)$, where $ 0\leq a,b\leq 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: Let us count the number of pairs $({\bf line},{\bf point})$ on two ways.
- Say we have $l$ lines and each can pass at most $n+1$ points. Say $k$ of them pass through $n+1$ points, then $k\leq 2n+1$. So all of them pass at most through $$k(n+1)+n(l-k) \leq (l+2)n+1$$ points, so we have at most $(l+2)n+1$ pairs $({\bf line},{\bf point})$.
- On the other hand all points pass at least thorugh $$\sum_{a=0}^n\sum_{b=0}^n (a+b+1)-1 = n^3+3n^2+3n $$ lines, so we have at list that many pairs $({\bf line},{\bf point})$.
- So we have $$n^3+3n^2+3n\leq (l+2)n+1\implies l\geq n(n+3)$$ and thus a conclusion.
Is there a polynomial aproach to this problem? (Like defining some polynomials which wanish on some set of points...)
There are alebraic proofs for a general statement, but in 2-dimension they are more involving than the elementary ways. (In higher dimension I know only algebraic methods.) I would not call it linear algebra; it is much closer to Hermite interpolation and divided differences.
The origin of this problem family is a paper of Alon and Füredi, Covering the Cube by Affine Hyperplanes. The most popular variant is IMO problem 2007/6. I asked this multi-set variant in the KöMaL contest, Problem A. 510. in 2010. A set of more general statements can be found here; the current question is a particular case of Theorem 12.
Instead of remaking a full proof, let me give you an outline only. The main idea is that we define a polynomial $P(x,y)$ that is the product of equations of the lines. This polynomial satisfies $P(0,0)\ne0$ and $\frac{\partial^i}{\partial x^i}\frac{\partial^j}{\partial x^j}P(a,b)=0$ whenever $0\le a,b\le n$, $a+b>0$ and $i+j\le a+b$. Already these properties imply that $\deg P\ge n(n+3)$.
$\textbf{Lemma 1d:}$ There is a unique set of real numbers $c_{i,j}$ ($0\le j\le i\le n$) with the following property: for every polynomial $p(x)=a_0+\ldots+a_{n(n+3)/2}x^{n(n+3)/2}$ we have $a_{n(n+3)/2}=\sum_{0\le j\le i} p^{(i)}(j)$. Moreover, $c_{0,0}\ne0$.
A possible proof is expanding the Taylor coefficient / divided difference $$ a_{n(n+3)/2} = f[0,1,1,2,2,2,\ldots,\underbrace{n,\ldots,n}_{n+1}] = \sum_{0\le j\le i\le n}c_{i,j}f^{(j)}(i).$$ It is easy to compute the coefficients $c_{i,i}$ (with $i=j$) explicitly; in particular, $c_{0,0}=\frac{1}{(-1)^2(-2)^3\cdots(-n)^{n+1}}$.
$\textbf{Lemma 2d:}$ Suppose that $p(x,y)=\sum a_{u,v}x^uy^v$ is a polynomial with degree at most $n(n+3)$. Then the coefficient of $(xy)^{n(n+3)/2}$ in $p$ is $$ a_{n(n+3)/2,n(n+3)/2} = \sum_{0\le j\le i\le n}\sum_{0\le k\le l\le n} c_{i,j}c_{k,\ell} \frac{\partial^{j+\ell}}{\partial x^j\partial y^\ell} p(i,k). $$
Proof: Just apply Lemma 1d to each monomial in $p$.
$\textbf{Corollary:}$ $\deg P\ge n(n+3)$, so the number of lines is at least $\deg P\ge n(n+3)$.
Proof: By Lemma 2d, the coefficient of $(xy)^{n(n+3)/2}$ in $P(x,y)$ is nonzero.