Results 1 to 2 of 2

Math Help - Pigeon Hole Principle Question

  1. #1
    Newbie
    Joined
    Mar 2009
    Posts
    6

    Question Pigeon Hole Principle Question

    Utilizing the pigeon hole principle answer the following question:

    show that if any 9 digit integers are chosen from 1 to 16, then two of them will add up to 17
    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 fusion1455 View Post
    Utilizing the pigeon hole principle answer the following question:

    show that if any 9 digit integers are chosen from 1 to 16, then two of them will add up to 17
    what have you tried? note that if the digits are listed in order from 1 up to 16, then the nth number, and then (17 - n)th number (for n ranging from 1 to 8) sum to 17. so then, we can pair off integers in the list that sum to 17. there are 8 such pairs. if we pick numbers so that we do not pick 2 numbers from the same pair, the most we could pick is 8, because upon picking the ninth number, we would have picked a number that pairs off with one of the other numbers to make 17. confused? so am i. take this instead. let the pigeons be the digits, let the holes be the pairs. every time you select a digit (pigeon) place it in the hole that corresponds to the pair it belongs to. since there are 8 pairs in total, namely (1,16),(2,15), (3,14), (4,13), (5,12), (6,11), (7,10), (8,9), if you pick 9 integers, you will have to reuse one of the holes, since you only have 8 of them
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. pigeon-hole principle
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: February 16th 2011, 01:15 AM
  2. Pigeon Hole Principle
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 28th 2009, 08:22 PM
  3. Pigeon Hole Principle
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 31st 2009, 08:59 AM
  4. pigeon hole principle
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 16th 2008, 04:39 AM
  5. Pigeon Hole Principle Question
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: April 6th 2008, 08:42 AM

Search Tags


/mathhelpforum @mathhelpforum