A Pigeon-Hole Problem and an Irrational Root Problem

I'm not sure what category these belong in. They're somewhat like puzzles.

3. A town has 2001 residents. Each resident has a non-negative amount of money (integer). If no two residents have the same amount of money and the combined sum of the balance of any 1000 residents is less than the combined sum of the balances of the remaining 1001 residents. Show that every resident has at least 1,000,000.

4. Show that for every integer n >= 2, the polynomial f(x) = x^n + (n^2+1)x + n has at least one root which is not a rational number

Re: A Pigeon-Hole Problem and an Irrational Root Problem

Solution to 4:

Lemma. If $p(x)=x^n+a_1x^{n-1}+\cdots+a_{n-1}x+a_n$ is a monic polynomial with coefficients in $\mathbb Z[x]$ and it has a rational root, $x_0 = \frac{p}{q}$ then $x_0$ is an integer.

Proof. Assume the statement is not true: $\gcd(p,q)=1$ and $q>1$. Then

\[(\frac{p}{q})^{n}+a_{n-1}(\frac{p}{q})^{n-1}+\cdots +a_n=0\]

and

\[p^n+ a_{n-1}p^{n-1}q+\cdots+a_nq^n=0.\]

Looking modulo $q$ we get $q \mid p^n$, a contradiction.

Returning back to our problem, assume all roots are rational.

Using our lemma, we know that all roots of $f(x) = x^n + (n^2+1)x + n$ are non-zero integers.

Suppose $x_1, \ldots, x_n$ are roots of $f(x)=(x-x_1)\cdots (x-x_n)$ and $|x_i| \geq 1$.

Using Viete's formulae we know that $\prod_{i=1}^{n}x_i= (-1)^{n}n$ and

$\sum_{i=1}^{n} \frac{1}{x_i} = -\frac{n^2+1}{n}$.

Thus

\[n \geq \sum_{i=1}^{n}\frac{1}{|x_i|} \geq |\sum_{i=1}^{n} \frac{1}{x_i}| =|\frac{n^2+1}{n}|,\]

a contradiction.