Results 1 to 5 of 5

Math Help - Combinatorics HELP

  1. #1
    Newbie
    Joined
    Apr 2008
    Posts
    2

    Combinatorics HELP

    Let a1, a2, a3, a4 ,a5, be any distinct positive integers. Show that there exists at least one subset of three integers whose sum is divisible by 3.

    what is the answer to this...plzz HELPP!!!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by fafafa View Post
    Let a1, a2, a3, a4 ,a5, be any distinct positive integers. Show that there exists at least one subset of three integers whose sum is divisible by 3.

    what is the answer to this...plzz HELPP!!!
    Have you ever heard of the Pigeon Hole principle? You can use that here.

    Note that any positive integer is either congruent to 0 mod 3 or 1 mod 3 or 2 mod 3. we have more than three integers here, so we know all congruences are accounted for. Further more, at least one congruence repeats. Try doing this by cases. (There may be an easier way, I'm not a Number Theorist)

    Any questions? Do you have an idea of how to proceed?

    EDIT: Ah, nevermind, I just realized this post makes no sense! Nothing is stopping us from choosing all the numbers of one congruence class
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Apr 2008
    Posts
    2
    i have no idea what to do..is it possible you can show me the answer step by step plz...
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Hello,

    Here are the possibilities :

    0-0-0 -> ok
    0-0-1 -> not ok


    What are the conditions upon those integers ? Consecutive ?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member angel.white's Avatar
    Joined
    Oct 2007
    Posts
    723
    Awards
    1
    You have 5 integers.

    Each integer must be congruent to either 0, 1, or 2 (mod 3).

    if any 3 are congruent (mod 3), then 3 divides their sum
    ie 5 + 5 + 5 = 3+2 + 3+2 + 3+2 = 3(3+2)

    and if all 3 mods are represented, then 3 divides their sum
    ie 5 + 6 + 7 = 3+2 + 3+3 + 3+4 = 3+(3-1) + 3+(3+0) + 3+(3+1) = 3*3 + (3*3 -1+0+1) = 3*3 + 3*3 = 3(3+3)

    *note, those examples are for your understanding, I wouldn't put them in your proof, if you need to show this, show it in a more abstract way that can be applied to any given situation*

    So worst case, two are congruent to 0, or 1, or 2 (mod 3) and two more are congruent to 0, or 1, or 2 (mod 3), but these two sets of numbers are not congruent to eachother (mod 3). Then if the 5th term is congruent to either of these sets, 3 will divide their sum. The only alternative is that it is not congruent to any of the other numbers (mod 3) in which case, all three mods are represented, and so any combination of a 0, 1, and 2 (mod 3) will sum to a number divisible by 3.
    Last edited by angel.white; April 13th 2008 at 10:42 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Combinatorics.
    Posted in the Discrete Math Forum
    Replies: 16
    Last Post: July 20th 2010, 02:29 AM
  2. Combinatorics
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: June 18th 2010, 08:14 PM
  3. Combinatorics
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: June 3rd 2010, 05:24 PM
  4. combinatorics
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 1st 2010, 10:53 PM
  5. Combinatorics
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 10th 2009, 06:03 AM

Search Tags


/mathhelpforum @mathhelpforum