Results 1 to 10 of 10

Math Help - Integer proof

  1. #1
    Junior Member
    Joined
    Oct 2009
    Posts
    51

    Integer proof


    Any ideas (I have been struggling with this one for a while)?
    Last edited by mr fantastic; May 1st 2010 at 03:11 PM. Reason: Edited post title.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2008
    From
    France
    Posts
    1,458
    Hi

    The nine integer can be considered by their rest in the division by 5
    There are 5 classes of rests : 0, 1, 2, 3 and 4

    If 4 classes are empty, the nine integers are of the same class then any set of 5 integers works

    If 3 classes are empty, then one of the 2 non-empty class has 5 integers. This set works

    If 2 classes are empty :
    - if 1 of the 3 non-empty class has only 1 integer then we have to consider the case where the 2 other classes have 4 integers (in the other cases one of the classes has 5 or more integers)
    I do not see any other way than consider all the cases :
    class 0 : 1 integer
    class 1 : 4 integers
    class 2 : 4 integers
    ==> 0-1-1-1-2 works

    class 0 : 1 integer
    class 1 : 4 integers
    class 3 : 4 integers
    ==> 0-1-3-3-3 works

    class 0 : 1 integer
    class 1 : 4 integers
    class 4 : 4 integers
    ==> 0-1-1-4-4 works

    class 0 : 1 integer
    class 2 : 4 integers
    class 3 : 4 integers
    ==> 0-2-2-3-3 works

    class 0 : 1 integer
    class 2 : 4 integers
    class 4 : 4 integers
    ==> 0-2-2-2-4 works

    class 0 : 1 integer
    class 3 : 4 integers
    class 4 : 4 integers
    ==> 0-3-4-4-4 works

    class 1 : 1 integer
    class 0 : 4 integers
    class 2 : 4 integers
    ==> 0-0-1-2-2 works

    class 1 : 1 integer
    class 0 : 4 integers
    class 3 : 4 integers
    ==> 0-1-3-3-3 works

    class 1 : 1 integer
    class 0 : 4 integers
    class 4 : 4 integers
    ==> 0-0-0-1-4 works

    class 1 : 1 integer
    class 2 : 4 integers
    class 3 : 4 integers
    ==> 1-2-2-2-3 works

    class 1 : 1 integer
    class 2 : 4 integers
    class 4 : 4 integers
    ==> 1-2-4-4-4 works

    class 1 : 1 integer
    class 3 : 4 integers
    class 4 : 4 integers
    ==> 1-3-3-4-4 works

    etc ...

    - if 1 of the 3 non-empty class has only 2 integers then we have to consider the cases where the 2 other classes have 3 and 4 integers (in the other cases one of the classes have 5 or more integers)
    class 0 : 2 integers
    class 1 : 3 integers
    class 2 : 4 integers
    ==> 0-0-1-2-2 works

    class 0 : 2 integers
    class 1 : 4 integers
    class 2 : 3 integers
    ==> 0-1-1-1-2 works

    etc ...

    - the last case is : the 3 classes have 3 integers
    class 0 : 3 integers
    class 1 : 3 integers
    class 2 : 3 integers
    ==> 0-1-1-1-2 works

    class 0 : 3 integers
    class 1 : 3 integers
    class 3 : 3 integers
    ==> 0-1-3-3-3 works

    class 0 : 3 integers
    class 1 : 3 integers
    class 4 : 3 integers
    ==> 0-1-1-4-4 works

    etc ...

    Consider the 2 other cases : 1 class empty and 0 class empty

    It is a bit of work ...
    There may be a simplest solution
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Oct 2009
    Posts
    51
    WOW! That looks complicated - is there any simpler, neater solution, by any chance?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Apr 2010
    Posts
    61
    You should be able to reduce your problem to the following: Given 9 elements of \mathbb{Z}_5 it is always possible to select 5 which sum to 0.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Oct 2009
    Posts
    51
    Could you please explain that in simpler terms?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Aug 2008
    Posts
    91
    First note that the sum of any five consecutive integers is divisible by 5, and that is because x+(x+1)+(x+2)+(x+3)+(x+4)=5(x+2) .
    Note that among the components of the sum there are 0,1,2,3,4 \equiv \mod 5. Of course 0+1+2+3+4\equiv 0 \mod 5.
    Using the pigeonhole principle, among any nine integers there is at least one integer that is equal to 0,1,2,3 or 4 \mod 5. It's enough to pick those five and there we get a sum divisible by 5.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Oct 2009
    Posts
    51
    Could you please explain to me what this triple equals sign means, and also what this 'mod' means?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Aug 2008
    Posts
    91
    You may google 'congruence', 'modular arithmetic' for more on that topic.
    As you don't know it yet, it might be simpler to put it that way: any integer you choose yields one of four different remainders in division by 5 (0,1,2,3 and 4). If you choose nine integers, then by pigeonhole principle at least one of them gives each of these five remainders in division by 5, so 0-1-2-3-4-2-3-4-4, 0-1-2-3-4-1-2-3-4 (or any combination in which 0-1-2-3-4 is contained). So you need to pick five numbers that each give a different remainder in division by zero, and sum them.
    Last edited by atreyyu; May 1st 2010 at 02:04 PM.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Junior Member
    Joined
    Oct 2009
    Posts
    51
    Would there, by any chance, be any other simpler way of doing this?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Member
    Joined
    Aug 2008
    Posts
    91
    Really, once you put your fingers on the topic of congruence, this is the simplest way.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Integer Proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 2nd 2010, 01:53 AM
  2. gcd integer proof
    Posted in the Calculus Forum
    Replies: 1
    Last Post: November 6th 2009, 12:20 PM
  3. Simple integer proof
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: September 14th 2009, 05:26 PM
  4. Integer Proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 1st 2009, 11:09 AM
  5. Integer Proof
    Posted in the Algebra Forum
    Replies: 0
    Last Post: October 23rd 2008, 12:36 PM

Search Tags


/mathhelpforum @mathhelpforum