Results 1 to 14 of 14

Math Help - Pigeonhole Theorem

  1. #1
    Senior Member
    Joined
    Apr 2009
    Posts
    289

    Pigeonhole Theorem

    A form of the pigeonhole theorem is stated as "If f is a function from a finite set X to a finite set Y with |X| > |Y| then f(x_1) = f(x_2) for some x_1, x_2 \in X, x_1 \neq x_2

    Now a question says: An inventory consists of a list of 89 items, each marked "available" or "unavailable". There are 45 available items, show that there are at least two available items in the list exactly 9 items apart.

    Now I just don't know how to apply the pigeonhole theorem to this question, what is set X and Y in this case? And what is the function?

    Many thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,390
    Thanks
    1476
    Awards
    1
    Please check the wording of this problem.
    I think the it must be 80 items and not 89.

    PS. That is a typo. Otherwise I think there is a counterexample.
    Last edited by Plato; July 19th 2010 at 01:21 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1
    Can someone please translate this question to Hebrew(especially the last part...)?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Apr 2009
    Posts
    289
    Thanks guys, I have rechecked the question, that is exactly what it says :S
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Apr 2009
    Posts
    677
    if it is 80 here is a hint

    split all the numbers into to 9 buckets (using modulo 9)

    how many maximum numbers can you select from each bucket?

    Note: I have been thinking about how to explicitly express this in terms of the statement of the pigeon-hole principle - but couldn't make much progress. Maybe someone on this froum can help
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Apr 2009
    Posts
    289
    Thanks again, actually the question also said (For example items at position 13 and 22 satisfy the condition) and I assume by 89 items they are listed in position from 1-89.

    Does this help?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by usagi_killer View Post
    Thanks again, actually the question also said (For example items at position 13 and 22 satisfy the condition) and I assume by 89 items they are listed in position from 1-89.

    Does this help?
    So the source really says 89? Counterexample

    {1, 2, 3, 4, 5, 6, 7, 8, 9, 19, 20, 21, 22, 23, 24, 25, 26, 27, 37, 38, 39, 40, 41, 42, 43, 44, 45, 55, 56, 57, 58, 59, 60, 61, 62, 63, 73, 74, 75, 76, 77, 78, 79, 80, 81}
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Senior Member
    Joined
    Apr 2009
    Posts
    289
    Yeah I got that counter example too, the solutions do it like this: (It makes sense so I don't know where the fallacy is)

    Let a_i denote the position of the ith available item. We must show that a_i-a_j = 9 for some i and j. Consider the numbers:

    a_1, a_2, \cdots, a_{45} ...[1]

    and

    a_1+9, a_2+9, \cdots. a_{45}+9 ...[2]

    The 90 numbers from [1] and [2] have possible values from 1-89. So by the form of the pigeonhole theorem I stated in the OP, two numbers must coincide. We cannot have two of [1] or two of [2] identical, thus some number in [1] is equal to some number in [2]. Therefore a_i = a_j+9 \implies a_i-a_j = 9 for some i and j.

    Now I understand their working but obviously there exists a counterexample, so where is the fallacy in their working?

    Many thanks again!
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by usagi_killer View Post
    Yeah I got that counter example too, the solutions do it like this: (It makes sense so I don't know where the fallacy is)

    Let a_i denote the position of the ith available item. We must show that a_i-a_j = 9 for some i and j. Consider the numbers:

    a_1, a_2, \cdots, a_{45} ...[1]

    and

    a_1+9, a_2+9, \cdots. a_{45}+9 ...[2]

    The 90 numbers from [1] and [2] have possible values from 1-89. So by the form of the pigeonhole theorem I stated in the OP, two numbers must coincide. We cannot have two of [1] or two of [2] identical, thus some number in [1] is equal to some number in [2]. Therefore a_i = a_j+9 \implies a_i-a_j = 9 for some i and j.

    Now I understand their working but obviously there exists a counterexample, so where is the fallacy in their working?

    Many thanks again!
    That wording could be better, but anyway here's an obvious flaw: the numbers in [1] must be in {1, ..., 89} and the numbers in [2] must be in {10, ... , 98}. So, a function from a set with cardinality 90 to a set with cardinality 98 need not have a duplicate.

    That makes me realize how to apply pidgeonhole to the real problem when we have 80 items in our inventory. You do the same steps but you get that you're trying to fit 90 elements into a set with cardinality 89.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Senior Member
    Joined
    Apr 2009
    Posts
    289
    Oh right, that makes sense!

    Thanks very much!!
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Super Member
    Joined
    Apr 2009
    Posts
    677
    Quote Originally Posted by undefined View Post
    That wording could be better, but anyway here's an obvious flaw: the numbers in [1] must be in {1, ..., 89} and the numbers in [2] must be in {10, ... , 98}. So, a function from a set with cardinality 90 to a set with cardinality 98 need not have a duplicate.

    That makes me realize how to apply pidgeonhole to the real problem when we have 80 items in our inventory. You do the same steps but you get that you're trying to fit 90 elements into a set with cardinality 89.
    @undefined - sorry but can you elaborate the proof for "That makes me realize how to apply pidgeonhole to the real problem when we have 80 items in our inventory. You do the same steps but you get that you're trying to fit 90 elements into a set with cardinality 89". I haven't been able to follow it please.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,390
    Thanks
    1476
    Awards
    1
    I knew that I had seen this question before.
    It is worked out as as example on page 250 of the fourth edition of Discrete Mathematics by Johnsonbaugh.
    And it is 80 items and not 89.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by aman_cc View Post
    @undefined - sorry but can you elaborate the proof for "That makes me realize how to apply pidgeonhole to the real problem when we have 80 items in our inventory. You do the same steps but you get that you're trying to fit 90 elements into a set with cardinality 89". I haven't been able to follow it please.
    Sure. So this is just post #8 rewritten slightly.

    Label the items {1, 2, ... , 80}. Let \displaystyle A = \{a_1, a_2,\,\dots\,,a_{45}\} be the set of available items. The elements of A are distinct and in the range {1, 2, ... , 80}. Let B = \displaystyle \{a_1+9, a_2+9,\,\dots\,,a_{45}+9\}. Likewise the elements of B are distinct and in the range {10, 11, ... , 89}. Let \displaystyle X = A \cup B. So X is composed of elements in the range {1, 2, ... , 89}. But we started with 90 elements (45 from A and 45 from B), so by the pidgeonhole principle, at least two of those 90 elements are identical. Since the elements of A and B are distinct, we must have some \displaystyle a_i \in A that is identical to some \displaystyle a_j + 9 \in B. QED.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Senior Member
    Joined
    Apr 2009
    Posts
    289
    Quote Originally Posted by Plato View Post
    I knew that I had seen this question before.
    It is worked out as as example on page 250 of the fourth edition of Discrete Mathematics by Johnsonbaugh.
    And it is 80 items and not 89.
    Yeah I have the 7th international edition, says 89 for some reason haha
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Pigeonhole Proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 9th 2011, 10:00 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: 3
    Last Post: October 26th 2008, 09:09 AM
  5. Pigeonhole problem
    Posted in the Advanced Statistics Forum
    Replies: 4
    Last Post: October 18th 2008, 02:41 PM

Search Tags


/mathhelpforum @mathhelpforum