Results 1 to 9 of 9

- Jul 1st 2007, 07:05 PM #1

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

## 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.

- Jul 1st 2007, 07:41 PM #2

- Joined
- Nov 2005
- From
- someplace
- Posts
- 14,972
- Thanks
- 5

- Jul 1st 2007, 08:00 PM #3

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

- Jul 2nd 2007, 02:23 AM #41)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.

- Jul 2nd 2007, 06:36 AM #5

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

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.

- Jul 2nd 2007, 08:18 AM #6

- 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.

- Jul 2nd 2007, 08:33 AM #7

- Joined
- Jun 2007
- Posts
- 18

#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.

- Jul 9th 2007, 12:28 PM #8

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

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.

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.

- Dec 29th 2007, 04:06 AM #9
It is fun going over all these nice, old problems.

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!