Results 1 to 7 of 7

Math Help - Pigeonhole principle

  1. #1
    Newbie
    Joined
    Mar 2009
    Posts
    2

    Pigeonhole principle

    Not sure if this belongs here or in discrete.

    Find all triples of positive integers a<b<c for which (1/a)+(1/b)+(1/c)=1 holds.

    Have no idea how to get started on this. Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    May 2009
    Posts
    74
    It given that <br />
a<b<c \quad \quad [1]<br />

    Why dont you get started by solving the equality:

    <br />
\frac{1}{a}+\frac{1}{b}+\frac{1}{c}=1 \Rightarrow \quad \quad [2]<br />

    <br />
\frac{a+b+c}{a\cdot b \cdot c}=1<br />

    or else

    <br />
{a+b+c}={a\cdot b \cdot c}\quad \quad [3]<br />

    Next assume that:
    <br />
b = a+B<br />
    <br />
c = a+C<br />

    By expanding the equation [3] we have that
    <br />
3a+B+C = a^3+a^2B+a^2C+aBC<br />

    Since all are possitive integers we compare addition terms seperate:

    3a<a^3 for any a>1
    B<a^2B for any a>1
    C<a^2C for any a>1

    So we conclude that
    <br />
3a+B+C < a^3+a^2B+a^2C+aBC<br />
for a>1

    Finally if a=1 then
    <br />
3+B+C = 1+B+C+BC \Rightarrow<br />
BC=2<br />

    The last cannot hold because 1<B<C

    So there is no such combination of positive integers that satisfy [1] and [2] conditions
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by rectril View Post
    Not sure if this belongs here or in discrete.

    Find all triples of positive integers a<b<c for which (1/a)+(1/b)+(1/c)=1 holds.

    Have no idea how to get started on this. Thanks.
    Hint: The mention of the pigeonhole principle may be a red herring-- you may not need it here!

    Can we have a \geq 3? If so, then b \geq 4 and c \geq 5. So 1/a \leq 1/3,
    1/b \leq 1/4, and 1/c \leq 5, hence 1/a + 1/b + 1/c \leq 1/3 + 1/4 + 1/5. Doesn't look good...

    So we must have a = 1 or a = 2. Analyze these cases separately and see where they lead you.
    Last edited by awkward; August 30th 2009 at 07:19 AM. Reason: Can't spell principle!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    May 2009
    Posts
    74
    Sorry BIG mistake
    [2] leads at:
    <br />
\frac{ab+bc+ac}{abc}=1<br />

    do not know how i missed that!
    then this leads to:
    <br />
3a^2 + 2(B+C)a +BC= a^3+a^2B+a^2C+aBC\Rightarrow<br />

    <br />
3a^2 + 2(B+C)a +BC= a^3+(B+C)a^2+aBC\Rightarrow<br />
    <br />
3a^2 + 2(B+C)a +BC= a(a^2+(B+C)a+BC)<br />

    I am working on it,
    post you when i have something new

    Sorry again
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Mar 2009
    Posts
    2
    Quote Originally Posted by awkward View Post
    Hint: The mention of the pigeonhole principle may be a red herring-- you may not need it here!

    Can we have a \geq 3? If so, then b \geq 4 and c \geq 5. So 1/a \leq 1/3,
    1/b \leq 1/4, and 1/c \leq 5, hence 1/a + 1/b + 1/c \leq 1/3 + 1/4 + 1/5. Doesn't look good...

    So we must have a = 1 or a = 2. Analyze these cases separately and see where they lead you.
    a can't be 1 since there are no b and c that can possibly satisfy the equation, so a must be 2. So 1/b + 1/c = 1/2. Choose b = 3 and solve for c. a = 2, b = 3, c = 6 satisfy the equation.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by rectril View Post
    a can't be 1 since there are no b and c that can possibly satisfy the equation, so a must be 2. So 1/b + 1/c = 1/2. Choose b = 3 and solve for c. a = 2, b = 3, c = 6 satisfy the equation.
    That is good, but the problem says to find all solutions in positive integers.

    So can you find more solutions? Or if not, can you prove the one you found is the only one?
    Last edited by awkward; August 30th 2009 at 04:04 PM. Reason: omitted word
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Aug 2009
    Posts
    170
    Thanks
    8
    can't be 1 since there are no and that can possibly satisfy the equation, so must be 2. So .
    Since a=2 we have that b \geq 3.

    Following awkwards' procedure, we check if there's an upper limit for b, and there is indeed. If b \geq 4 then c \geq 5 and we have that 1/b + 1/c \leq 1/4 + 1/5 < 1/2

    So b \leq 3 and since b \geq 3, we have that b = 3 which rectril has solved for already
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. help me with pigeonhole principle #2
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: October 31st 2009, 11:23 PM
  2. help me with pigeonhole principle #1
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 31st 2009, 03:58 PM
  3. Pigeonhole principle
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: January 31st 2009, 03:59 PM
  4. Pigeonhole Principle
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: August 30th 2007, 03:15 PM
  5. Pigeonhole Principle
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: January 23rd 2006, 06:09 PM

Search Tags


/mathhelpforum @mathhelpforum