Results 1 to 4 of 4
Like Tree1Thanks
  • 1 Post By IvanBorsenco

Math Help - A Pigeon-Hole Problem and an Irrational Root Problem

  1. #1
    Newbie
    Joined
    Jun 2011
    Posts
    2

    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
    Last edited by Ackbeet; June 1st 2011 at 08:06 AM. Reason: Splitting thread.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    May 2011
    Posts
    22
    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....
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    May 2011
    Posts
    22
    Wowee, I cannot do number 4. I'm too stupid after all. No one million dollar/yen/dead rat reward for me.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Mar 2013
    From
    Boston
    Posts
    1
    Thanks
    1

    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.
    Thanks from emakarov
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. pigeon-hole principle
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: February 16th 2011, 01:15 AM
  2. Pigeon Hole Principle
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 28th 2009, 08:22 PM
  3. pigeon-hole
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: December 11th 2008, 02:41 PM
  4. Pigeon Hole problem!
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 29th 2008, 10:10 AM
  5. Pigeon hole-proof
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 11th 2008, 02:02 AM

Search Tags


/mathhelpforum @mathhelpforum