Results 1 to 11 of 11

Thread: 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
    21,742
    Thanks
    2814
    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
    11,124
    Thanks
    720
    Awards
    1
    Consider a set of n integers. Put all of them in the form
    $\displaystyle n_i = (n - 1)a_i + k_i$

    Represent each element by its corresponding $\displaystyle k _i$ value.

    At best we may select n - 1 of these $\displaystyle k_i$ values (and hence $\displaystyle n_i$ values) such that the difference between any two of them is not divisible by n - 1 simply by choosing all values of $\displaystyle k_i$ to be different. (Because if $\displaystyle k_j = k_i$ for some $\displaystyle 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 $\displaystyle k_i$ values. (Because only n - 1 different $\displaystyle k_i$ values exist.)

    So our list of n integers must include two elements $\displaystyle 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:
    $\displaystyle n_i = (n - 1)a_i + k_i$

    2- What are $\displaystyle a _i$'s and $\displaystyle 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 $\displaystyle 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 $\displaystyle 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
    11,124
    Thanks
    720
    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 $\displaystyle 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 $\displaystyle k_i$'s and not n-1 in the example above, namely (-3, -2, -1, 0, 1)!

    Am I missing something?
    Yes, the $\displaystyle a_i$ and $\displaystyle k_i$ are integers. Let me put all the $\displaystyle 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 $\displaystyle 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: $\displaystyle n_i = (n-1)a_i + k_i$ such that $\displaystyle a_i$, $\displaystyle k_i$ are integers and $\displaystyle k_i$ >= 0.

    2- How do you prove that in the original problem the number of different $\displaystyle 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
    21,742
    Thanks
    2814
    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 $\displaystyle 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 $\displaystyle k_i$ be the pigeonholes. The $\displaystyle k_{n-2} < {n-1}$ so we are putting $\displaystyle n$ pigeons into $\displaystyle 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
    10
    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 $\displaystyle n+1$ positive integers there are two whose difference is multiple of $\displaystyle n$.

    The demonstration will be complete if we can show that two numbers have the same remainder upon division by $\displaystyle n$. Since there are $\displaystyle n+1$ integers there must be at least two "pigeons" in two "pigeonholes". Meaning two numbers that leave the same remainder upon division by $\displaystyle 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: Oct 20th 2011, 03:46 PM
  2. a pigeonhole problem
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: Oct 11th 2010, 01:33 AM
  3. Pigeonhole Problem
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Dec 15th 2009, 04:31 PM
  4. pigeonhole problem ... ASAP please
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Oct 29th 2008, 11:03 PM
  5. Pigeonhole problem
    Posted in the Advanced Statistics Forum
    Replies: 4
    Last Post: Oct 18th 2008, 02:41 PM

Search tags for this page

Click on a term to search for related topics.

Search Tags


/mathhelpforum @mathhelpforum