Results 1 to 9 of 9

Math Help - Problem 29

  1. #1
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10

    Problem 29

    1)In a room let there be n>1 people. Show that there must exist two people that shaked the same number of hands with others.

    2)Let a_1,a_2,...,a_n be distinct integers from \{1,2,...,n\} not necessarily in that order. Show that if n is odd then (a_1-1)(a_2-2)...(a_n-n) is an even number.
    Last edited by ThePerfectHacker; July 1st 2007 at 09:00 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by ThePerfectHacker View Post
    2)Let a_1,a_2,...,a_n be distinct integers from \{1,2,...,n\} not necessarily in that order. Show that if n is odd then (a_1-1)(a_2-1)...(a_n-1) is an even number.
    As a_1,a_2,...,a_n are distinct integers from \{1,2,...,n\} they are infact a permutation of \{1,2,...,n\}, so one of the a_i's is 1.

    Hence one of the terms (a_i-1) is zero so the product is zero, and so even irrespective of the parity of n.

    Or have I misread the question.

    RonL
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by CaptainBlank View Post
    Or have I misread the question.
    No. I forgot the rule "do not drink and derive".

    I will fix it now.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Eater of Worlds
    galactus's Avatar
    Joined
    Jul 2006
    From
    Chaneysville, PA
    Posts
    3,001
    Thanks
    1
    1)In a room let there be n>1 people. Show that there must exist two people that shaked the same number of hands with others.
    I was thinkin', PH, maybe we could make this a graph theory problem and call a person a vertex and a handshake an edge. Is that your approach?.

    I am certainly no expert graph theorist, but you can't have a graph with n vertices with a vertex having 0 degrees and another have n-1 degrees. So, therefore, hence, and heretofore, the most degrees the vertices can have is n-1 degrees. But since there's n vertices/vertexes, at least 2 have the same degree.

    I even drew a little graph to picture the handshakes.

    If I'm not right, I suppose I'll be wrong.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by galactus View Post
    I was thinkin', PH, maybe we could make this a graph theory problem and call a person a vertex and a handshake an edge. Is that your approach?.
    I am also no expert on graph theory. But I think you have a good approach.

    When I was working on this problem I drew it as a graph, but I did not use any graph theory at all. I think the graph just made it easier to think about because it makes the problem visiual. In fact, the solution is rather short, no need to use graph theory. Short elementray arguments are always the nicest.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Jun 2007
    Posts
    18
    Suppose that no two people shake hands the same number of times. Let k be the number of people who shake hands at least once. Order the people from 1 to k by their number of handshakes in ascending order. Each person must shake hands at least one more time than the person before him. Thus the kth person must have shaken hands at least k times. But there are only k people. Contradiction.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Jun 2007
    Posts
    18
    #1) For  \Pi _i (a_i-i) to be odd then each odd a_i must be subtracted by an even integer. Because n is odd, \{a_1, a_2, ..., a_n\} has one more odd than even integer. Similarly,  \{1, 2, ..., n \} has one less even integer than odd integer. So we must pair at least 1 odd integer a_i with an odd integer i. Hence the product is even.
    Last edited by mathisfun1; July 3rd 2007 at 01:41 PM.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    1)In a room let there be n>1 people. Show that there must exist two people that shaked the same number of hands with others.
    I found this nice problem as an excercise in a math book. We can solve this by induction. For n=2 it is clearly true. Either each one shook hands and in case the two people shaked hands zero times or each one shook hands an in which case both shook one hand. Now we will show that it is true for n+1. There are n+1 people in a room. Each one shook either 0,1,...,n hands, so there are n+1 possibilities and n+1 people. There are two cases: nobody shook 0 hands or somebody shook 0 hands. If nobody shook 0 hands then each person shook 1,...,n hands and by the Pigeonhole Principle two people shook the same number of hands. If somebody shook 0 hands then we have n people shaking hands among themselves, and by induction somebody shook the same number of hands.

    2)Let a_1,a_2,...,a_n be distinct integers from \{1,2,...,n\} not necessarily in that order. Show that if n is odd then (a_1-1)(a_2-2)...(a_n-n) is an even number.
    This was a competition problem from Hungray. The nicest solution to is consider the sum:
    (a_1-1)+(a_2-2)+...(a_n-n) = (a_1+...+a_n) - (1+2+...+n) = (1+...+n)-(1+...+n)=0
    Now there are n summands which add up to zero, an even integer. So it is impossible for all the numbers to be odd, since an odd sum of odd integers is still odd. So at least one is even. Hence (a_1-1)...(a_n-n) must be even.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    It is fun going over all these nice, old problems.

    Quote Originally Posted by ThePerfectHacker View Post
    I found this nice problem as an excercise in a math book. We can solve this by induction.
    Hey TPH,
    I think we can do this only using PHP, without induction(it is in fact akin to galactus solution)

    In the group of n people, The different possible handshakes for each person is
    0,1,2,3....,(n-1).
    Claim:
    We note that both 0 and n-1 together are not possible.
    Proof:
    Since handshake is symmetric, if there is a person with 0 handshake then nobody could have shook hands with this guy. Hence no one in the room would have shook hands with everyone. This implies "n-1" not possible.
    However if "n-1" case has happened, then some body shook hands with everyone and therefore everybody would have shaken non-zero hands. So 0 is not possible!
    That means "n-1" handshake choices for "n" people.
    Apply PHP and wrap it up.

    I think this argument is nice since it uses only PHP. We proved this result in graph theory using PHP itself!
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum