| 
07-01-2007, 09:05 PM
|  | Global Moderator | | Join Date: Nov 2005 Location: New York City
Posts: 11,339
Country: Thanks: 329
Thanked 2,943 Times in 2,472 Posts
| | Problem 29 1)In a room let there be  people. Show that there must exist two people that shaked the same number of hands with others.
2)Let  be distinct integers from  not necessarily in that order. Show that if  is odd then  is an even number.
__________________ We the People of the United States, in Order to form a more perfect Union, establish Justice, insure domestic Tranquility, provide for the common defence, promote the general Welfare, and secure the Blessings of Liberty to ourselves and our Posterity, do ordain and establish this Constitution for the United States of America.
Last edited by ThePerfectHacker; 07-01-2007 at 10:00 PM.
| 
07-01-2007, 09:41 PM
|  | Grand Panjandrum | | Join Date: Nov 2005 Location: Somewhere near the south coast
Posts: 10,102
Country: Thanks: 472
Thanked 2,598 Times in 2,162 Posts
| | Quote:
Originally Posted by ThePerfectHacker 2)Let  be distinct integers from  not necessarily in that order. Show that if  is odd then  is an even number. | As  are distinct integers from  they are infact a permutation of  , so one of the  's is  .
Hence one of the terms  is zero so the product is zero, and so even irrespective of the parity of  .
Or have I misread the question.
RonL
__________________ "It is proof of a base and low mind for one to wish to think with the masses or majority, merely because the majority is the majority"
--Giordano Bruno | | The following users thank CaptainBlack for this useful post: | |  | 
07-01-2007, 10:00 PM
|  | Global Moderator | | Join Date: Nov 2005 Location: New York City
Posts: 11,339
Country: Thanks: 329
Thanked 2,943 Times in 2,472 Posts
| | Quote:
Originally Posted by CaptainBlank Or have I misread the question. | No. I forgot the rule "do not drink and derive".
I will fix it now.
__________________ We the People of the United States, in Order to form a more perfect Union, establish Justice, insure domestic Tranquility, provide for the common defence, promote the general Welfare, and secure the Blessings of Liberty to ourselves and our Posterity, do ordain and establish this Constitution for the United States of America. | 
07-02-2007, 04:23 AM
|  | Eater of Worlds | | Join Date: Jul 2006 Location: Chaneysville, PA
Posts: 2,442
Country: Thanks: 88
Thanked 844 Times in 761 Posts
| | Quote:
1)In a room let there be 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. | 
07-02-2007, 08:36 AM
|  | Global Moderator | | Join Date: Nov 2005 Location: New York City
Posts: 11,339
Country: Thanks: 329
Thanked 2,943 Times in 2,472 Posts
| | Quote:
Originally Posted by galactus 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.
__________________ We the People of the United States, in Order to form a more perfect Union, establish Justice, insure domestic Tranquility, provide for the common defence, promote the general Welfare, and secure the Blessings of Liberty to ourselves and our Posterity, do ordain and establish this Constitution for the United States of America. | 
07-02-2007, 10:18 AM
| | Member | | Join Date: Jun 2007
Posts: 18
Country: Thanks: 0
Thanked 1 Time in 1 Post
| | 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. | 
07-02-2007, 10:33 AM
| | Member | | Join Date: Jun 2007
Posts: 18
Country: Thanks: 0
Thanked 1 Time in 1 Post
| | #1) For  to be odd then each odd  must be subtracted by an even integer. Because n is odd,  has one more odd than even integer. Similarly,  has one less even integer than odd integer. So we must pair at least 1 odd integer  with an odd integer  . Hence the product is even.
Last edited by mathisfun1; 07-03-2007 at 02:41 PM.
| 
07-09-2007, 02:28 PM
|  | Global Moderator | | Join Date: Nov 2005 Location: New York City
Posts: 11,339
Country: Thanks: 329
Thanked 2,943 Times in 2,472 Posts
| | Quote:
1)In a room let there be 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  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  . There are  people in a room. Each one shook either  hands, so there are  possibilities and  people. There are two cases: nobody shook  hands or somebody shook  hands. If nobody shook  hands then each person shook  hands and by the Pigeonhole Principle two people shook the same number of hands. If somebody shook  hands then we have  people shaking hands among themselves, and by induction somebody shook the same number of hands. This was a competition problem from Hungray. The nicest solution to is consider the sum: 
Now there are  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  must be even.
__________________ We the People of the United States, in Order to form a more perfect Union, establish Justice, insure domestic Tranquility, provide for the common defence, promote the general Welfare, and secure the Blessings of Liberty to ourselves and our Posterity, do ordain and establish this Constitution for the United States of America. | 
12-29-2007, 06:06 AM
|  | The Wannabe Shannon | | Join Date: Dec 2007 Location: Mostly in Algebra Textbooks
Posts: 1,017
Country: Thanks: 285
Thanked 430 Times in 372 Posts
| | It is fun going over all these nice, old problems. Quote:
Originally Posted by ThePerfectHacker 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! | | Thread Tools | | | | Display Modes | Linear Mode |
Posting Rules
| You may not post new threads You may not post replies You may not post attachments You may not edit your posts HTML code is Off | | | All times are GMT -7. The time now is 03:11 AM. | | |