Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

A pigeonhole problem

  1. Jun 12, 2007 #1

    I have this logic problem which I know should be solved by the pigeonhole principle but I was not successful in solving it after many tries and I hope someone here would help me out.

    The problem says:
    n integer numbers are given. Show that there are at least two numbers among them whose difference is multiple of n-1.
  2. jcsd
  3. Jun 12, 2007 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    How many pairs are there? How many remainders mod n-1 are there?
  4. Jun 12, 2007 #3
    That's all what the question said!
    I think it may need some other logic principles used along with the pigeonhole principle to solve it?
  5. Jun 12, 2007 #4
    Ok from counting principles: The numbers of pairs you can choose from a group of n elements (order does not matter here) is:

    (n // 2) i.e. n choose 2
    and that's = n!/((n-2)!2!) = ... = n(n-1)/2

    I got stuck right there!
    Last edited: Jun 12, 2007
  6. Jun 12, 2007 #5

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Have you met modulo, or clock, arithemetic? It is an important piece of mathematics, and one you were introduced to at the very start of your mathematics education: remainder arithmetic. Take one of those pairs. What is the remainder on division by n-1? It is one of 0,1,2,3,4,..,n-2 (e.g. after dividing by 8, you have remainder 0,1,2,3,4,5, or 7). Being divisible by n-1 means having remainder 0.

    Suppose I tell you that x-y has remainder r on division by n-1, and that x-z has remainder s, what is the remainder of z-y? Hint z-y = (x-y)-(x-z).
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook