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.
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?.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 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.
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.
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.
#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.
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.1)In a room let there be people. Show that there must exist two people that shaked the same number of hands with others.
This was a competition problem from Hungray. The nicest solution to is consider the sum:2)Let be distinct integers from not necessarily in that order. Show that if is odd then is an even number.
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.
It is fun going over all these nice, old problems.
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
We note that both 0 and n-1 together are not possible.
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!