Thread: 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

Ahhh, this is just the sort of completely pointless problem I used to like solving so much. Nothing like a contribution that doesn't benefit the human race one iota.

Let's suppose the people in town are lined up from poorest to wealthiest. The 1000 wealthiest have no more money than the 1001 poorest. Karl Marx would be very pleased with the distribution of wealth in this town. So we keep them in this demeaning line yet partition them into the 1000 wealthiest, set A, and 1001 poorest, set B. The minimum difference in wealth between the wealthiest and 1001st wealthiest person is 1000 dollars, because they are 1000 apart in ranking and no one has the same amount of money. Straight pidgeon hole principle there. The same is true of the 2nd and 1002nd wealthiest person, and the 3rd and 1003rd, etcetera, all the way down to the 1000th and 2000th. So the tiebreaker is the 2001st person, the poorest person in town, and he's in set B. It has already been established, however, that among the 1000 people in set A and the 1000 people in set B considered thusfar, since there are 1000 such people and each one in set B was accompanied by someone in set A who had at least 1000 dollars more, that so far set A is leading ahead of set B by 1000*1000 = 1000000 dollars (yen, juan, whatever) at least in total net worth. Thus the last person, the tiebreaker, who happens to be the poorest person in town, must have at least a million so that set B has at least as much total as set A. The poorest has at least 1000000, so everyone does. I'll think about number 4 now....

Wowee, I cannot do number 4. I'm too stupid after all. No one million dollar/yen/dead rat reward for me.

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.