Results 1 to 2 of 2

Math Help - Combinatorics

  1. #1
    Junior Member
    Joined
    Aug 2008
    Posts
    44

    Combinatorics

    Suppose you are given a set of 100 distinct positive integers. Show that there exist four intergers {a,b,c,d,} in this set such that a-b+c-d|2009.

    Sixteen distinct integers are choosen between 1 and 30 inclusive. Show that you can always find a pair of integers(among these 16) such that their difference is 3.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by Juancd08 View Post
    Suppose you are given a set of 100 distinct positive integers. Show that there exist four integers {a,b,c,d,} in this set such that a-b+c-d|2009.
    There must be some extra condition on the size of the integers in the set. Otherwise, you could have the numbers 10^{n+5}\quad(1\leqslant n\leqslant100). In any set of four of those numbers, the largest one would swamp the sum or difference of the other three. So a–b+c–d would be much larger than 2009, and could not be a factor of it.

    Quote Originally Posted by Juancd08 View Post
    Sixteen distinct integers are chosen between 1 and 30 inclusive. Show that you can always find a pair of integers(among these 16) such that their difference is 3.
    If you want to avoid pairs that differ by 3, then in the set 1,4,7,10,13,16,19,22,25,28 you could not pick any two consecutive elements. So the maximum number chosen from this set would be 5. Similarly for the sets 2,5,8,...,29 and 3,6,9,...,30, giving a total of at most 15 numbers altogether.
    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