Results 1 to 3 of 3

Math Help - Pigeonhole principle?

  1. #1
    MHF Contributor alexmahone's Avatar
    Joined
    Oct 2008
    Posts
    1,074
    Thanks
    7

    Pigeonhole principle?

    Let A consist of 16 elements of the set {1, 2, 3 ..., 106} so that no two elements of A differ by 6, 9, 12, 15, 18 or 21. Prove that two elements of A should differ by 3.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by alexmahone View Post
    Let A consist of 16 elements of the set {1, 2, 3 ..., 106} so that no two elements of A differ by 6, 9, 12, 15, 18 or 21. Prove that two elements of A should differ by 3.
    Let the pigeons be the 16 numbers that you choose. And let the holes be either 0 or 1 or 2, a number is determined in which hole it goes to by its remainder upon division by 3 (i.e. 17 goes into the 2 hole). This means that there are at least \left\lceil {16/3}\right\rceil = 6 elements in A that all have the same remainder upon division by three. Let us call these elements a_1 < a_2 < a_3 < a_4 < a_5 < a_6. Since these guys have the same remainder is means a_{i+1}-a_i is a multiple of three. Assume (for contradiction) that each a_{i+1} - a_i \not = 3 then it would mean a_{i+1} - a_i \geq 24 because it needs to be a multiple of three and one of 6,9,12,15,18 or 21 are allowed. But then this means a_6 - a_1 \geq (5)(24) = 120. This is a contradiction therefore there must be i so that a_{i+1} - a_i = 3.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor alexmahone's Avatar
    Joined
    Oct 2008
    Posts
    1,074
    Thanks
    7

    Smile

    Quote Originally Posted by ThePerfectHacker View Post
    Let the pigeons be the 16 numbers that you choose. And let the holes be either 0 or 1 or 2, a number is determined in which hole it goes to by its remainder upon division by 3 (i.e. 17 goes into the 2 hole). This means that there are at least \left\lceil {16/3}\right\rceil = 6 elements in A that all have the same remainder upon division by three. Let us call these elements a_1 < a_2 < a_3 < a_4 < a_5 < a_6. Since these guys have the same remainder is means a_{i+1}-a_i is a multiple of three. Assume (for contradiction) that each a_{i+1} - a_i \not = 3 then it would mean a_{i+1} - a_i \geq 24 because it needs to be a multiple of three and one of 6,9,12,15,18 or 21 are allowed. But then this means a_6 - a_1 \geq (5)(24) = 120. This is a contradiction therefore there must be i so that a_{i+1} - a_i = 3.
    Thanks so much for the prompt reply!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. help me with pigeonhole principle #2
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: October 31st 2009, 11:23 PM
  2. help me with pigeonhole principle #1
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 31st 2009, 03:58 PM
  3. Pigeonhole principle
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: January 31st 2009, 03:59 PM
  4. Pigeonhole Principle
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: August 30th 2007, 03:15 PM
  5. Pigeonhole Principle
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: January 23rd 2006, 06:09 PM

Search Tags


/mathhelpforum @mathhelpforum