Results 1 to 11 of 11

Math Help - A pigeonhole problem

  1. #1
    Newbie
    Joined
    Jun 2007
    Posts
    6

    Question A pigeonhole problem

    Hello,

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,607
    Thanks
    1574
    Awards
    1
    Quote Originally Posted by chem3 View Post
    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.
    Maybe you can't do because it is not true as stated.
    {1,2,3,4,5} are five integers where are the multiples of 4?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jun 2007
    Posts
    6
    Quote Originally Posted by Plato View Post
    Maybe you can't do because it is not true as stated.
    {1,2,3,4,5} are five integers where are the multiples of 4?
    By definition: K is a multiple of n means that => K = a.n for some integer a ~= 0.

    so, in your example: n = 5, n-1 = 4
    There are two numbers, namely 5,1 whose difference (4) is a nultiple of n-1 (4).
    4 = 1.4 (a is 1 here)
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,887
    Thanks
    326
    Awards
    1
    Consider a set of n integers. Put all of them in the form
    n_i = (n - 1)a_i + k_i

    Represent each element by its corresponding k _i value.

    At best we may select n - 1 of these k_i values (and hence n_i values) such that the difference between any two of them is not divisible by n - 1 simply by choosing all values of k_i to be different. (Because if k_j = k_i for some j \neq i then the difference between them would be zero, implying that the difference between the numbers they represent is a multiple of n - 1.)

    But we can't find any more than n - 1 different k_i values. (Because only n - 1 different k_i values exist.)

    So our list of n integers must include two elements k_j = k_i in which case the difference between them is a multiple of n - 1.

    -Dan
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Jun 2007
    Posts
    6
    Thanks ver much, topsquark!

    But there are some points I didn't get very well.

    1- How did you know that any integer (even or odd, positive or negative) can be written in the form:
    n_i = (n - 1)a_i + k_i

    2- What are a _i's and k _i's? Are they integers...?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Jun 2007
    Posts
    6
    OK, let's consider the set of 5 (n = 5) integers: {1,2,3,4,5}
    We can write the integers in the form n_i = (n-1)a_i + k_i as follows:

    1 = (5-1)1 + (-3) = 4 + (-3) = 1
    2 = (5-1)1 + (-2) = 4 + (-2) = 2
    3 = (5-1)1 + (-1) = 4 + (-1) = 3
    4 = (5-1)1 + (0) = 4 + (0) = 4
    5 = (5-1)1 + (1) = 4 + (1) = 5

    So there are n k_i's and not n-1 in the example above, namely (-3, -2, -1, 0, 1)!

    Am I missing something?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,887
    Thanks
    326
    Awards
    1
    Quote Originally Posted by chem3 View Post
    OK, let's consider the set of 5 (n = 5) integers: {1,2,3,4,5}
    We can write the integers in the form n_i = (n-1)a_i + k_i as follows:

    1 = (5-1)1 + (-3) = 4 + (-3) = 1
    2 = (5-1)1 + (-2) = 4 + (-2) = 2
    3 = (5-1)1 + (-1) = 4 + (-1) = 3
    4 = (5-1)1 + (0) = 4 + (0) = 4
    5 = (5-1)1 + (1) = 4 + (1) = 5

    So there are n k_i's and not n-1 in the example above, namely (-3, -2, -1, 0, 1)!

    Am I missing something?
    Yes, the a_i and k_i are integers. Let me put all the k_i's in your list to be positive numbers or 0:
    1 = 4*0 + 1
    2 = 4*0 + 2
    3 = 4*0 + 3
    4 = 4*1 + 0
    5 = 4*1 + 1

    There are only 4 possible k values: 0, 1, 2, and 3.

    My apologies for the confusion. This is better done by modular Mathematics and it's hard for me to translate them into something "more normal." Keep the k_i values as positive or zero, then the proof will go through more smoothly.

    -Dan
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Jun 2007
    Posts
    6
    This leaves two questions:

    1- How do prove that any integer can be written in the form: n_i = (n-1)a_i + k_i such that a_i, k_i are integers and k_i >= 0.

    2- How do you prove that in the original problem the number of different k_i values required to represent n integers is at most n-1.

    Thanks!
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,607
    Thanks
    1574
    Awards
    1
    I clearly misread you posting, sorry.
    Do you know the Division Algorithm? If a is an integer and d is a positive integer, then there are unique integers q and r such that a = qd + r,\quad 0 \le r < d. Now in your problem because n is assumed to be greater 2, n-1 is a positive integer. So on Danís example let the k_i be the pigeonholes. The k_{n-2} < {n-1} so we are putting n pigeons into n-1 holes.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Newbie
    Joined
    Jun 2007
    Posts
    6
    Thanks Plato!
    I got it now.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by chem3 View Post
    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.
    Let me state the problem a little differently.
    Given n+1 positive integers there are two whose difference is multiple of n.

    The demonstration will be complete if we can show that two numbers have the same remainder upon division by n. Since there are n+1 integers there must be at least two "pigeons" in two "pigeonholes". Meaning two numbers that leave the same remainder upon division by n. Q.E.D.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. pigeonhole principle problem
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 20th 2011, 03:46 PM
  2. a pigeonhole problem
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: October 11th 2010, 01:33 AM
  3. Pigeonhole Problem
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 15th 2009, 04:31 PM
  4. pigeonhole problem ... ASAP please
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 29th 2008, 11:03 PM
  5. Pigeonhole problem
    Posted in the Advanced Statistics Forum
    Replies: 4
    Last Post: October 18th 2008, 02:41 PM

Search Tags


/mathhelpforum @mathhelpforum