Pigeonhole Principle

Discussion in 'General Math' started by anheiserb, Oct 11, 2004.

  1. anheiserb

    anheiserb Guest

    Wow am I not understanding this problem. The book doesn't have any
    closely related examples. If someone can help me through this that
    would be great. Thanks, here is the problem:

    Let d be a positive integer. Show that among any group of d+1 (not
    necessarily consecutive) integers there are two with exactly the same
    remainder when they are divided by d.

    Jeff
     
    anheiserb, Oct 11, 2004
    #1
    1. Advertisements

  2. anheiserb

    Tim Brauch Guest

    wrote in 4ax.com:
    Remainder when divided by d means we are looking at the numbers modulo d.
    What are the possible residuals modulo d?

    And an even better question, show that there is at least one pair whose sum
    or difference is divisible by d (or is zero). Note, for this, d > 2.

    - Tim

    --
    Timothy M. Brauch
    NSF Fellow
    Department of Mathematics
    University of Louisville

    email is:
    news (dot) post (at) tbrauch (dot) com
     
    Tim Brauch, Oct 11, 2004
    #2
    1. Advertisements

  3. anheiserb

    anheiserb Guest

    Thanks Tim. Is this the correct piece for the modulo d -
    d+1 mod d
     
    anheiserb, Oct 11, 2004
    #3
  4. anheiserb

    Tim Brauch Guest

    wrote in
    To use the PHP, you have to identift the holes and the pigeons, then
    show that the number of holes is less than the number of pigeons. The
    PHP will never tell you which hole has two pigeons, only that there is
    such a hole. In fact, there might be one hole with all of the pigeons
    and that does not violate the PHP.

    To solve this problem, you have to decide what the holes are and what
    the pigeons are.

    A little hint: The pigeons are always what you are trying to say two of
    which are related somehow and the holes are always how to partition the
    relation.

    Bigger hint: You are trying to show two integers are related with the
    relation being the remainder after division by d.

    - Tim

    --
    Timothy M. Brauch
    NSF Fellow
    Department of Mathematics
    University of Louisville

    email is:
    news (dot) post (at) tbrauch (dot) com
     
    Tim Brauch, Oct 12, 2004
    #4
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.