Results 1 to 4 of 4

Math Help - Combinatorics and number theory

  1. #1
    Senior Member
    Joined
    Nov 2007
    Posts
    329

    Combinatorics and number theory

    10 integers are given. We know that there is no way of choosing some of them whose sum is divisible by 10. What can be the remainders of the 10 integers when divided by 10?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by james_bond View Post
    10 integers are given. We know that there is no way of choosing some of them whose sum is divisible by 10. What can be the remainders of the 10 integers when divided by 10?
    Hi james bond,

    No such collection of integers can exist.

    Let's say the integers are x_1, x_2, \dots , x_{10}. Consider the sums s_n = \sum_{i=1}^{10} x_i for n = 1, 2, \dots , 10. If any of the sums is divisible by 10 we're done, so let's suppose none of them are. Then the possible remainders of the sums are 1, 2, ..., 9. Since there are 10 sums and 9 possible remainders, at least two of the sums, say s_j and s_k, with j < k, have the same remainder, by the Pigeonhole Principle. Then \sum_{i=j+1}^k x_i is divisible by 10.
    Last edited by awkward; December 26th 2008 at 12:43 PM. Reason: Corrected lower limit on the final summation
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1
    Quote Originally Posted by awkward View Post
    Consider the sums s_n = \sum_{i=1}^{10} x_i for n = 1, 2, \dots , 10.
    Should this be:

    s_n = \sum_{i=1}^{n} x_i for n = 1, 2, \dots , 10?

    Grandad
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by Grandad View Post
    Should this be:

    s_n = \sum_{i=1}^{n} x_i for n = 1, 2, \dots , 10?

    Grandad
    Grandad,

    Yes, that was the idea but I didn't get it typed in right.

    Thanks for the correction.

    Awkward
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Textbooks on Galois Theory and Algebraic Number Theory
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: July 8th 2011, 06:09 PM
  2. Replies: 2
    Last Post: March 2nd 2011, 05:39 AM
  3. Combinatorics using the number of conjugate subgroups
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: August 23rd 2010, 10:14 PM
  4. Find the number of intersection points?(Combinatorics)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 30th 2009, 05:43 AM
  5. Replies: 2
    Last Post: December 18th 2008, 05:28 PM

Search Tags


/mathhelpforum @mathhelpforum