Problem 29

ThePerfectHacker · #1 $Old$ July 1st, 2007, 09:05 PM

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.

CaptainBlack · #2 $Old$ July 1st, 2007, 09:41 PM

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

ThePerfectHacker · #3 $Old$ July 1st, 2007, 10:00 PM

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.

galactus · #4 $Old$ July 2nd, 2007, 04:23 AM

Quote:

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.

ThePerfectHacker · #5 $Old$ July 2nd, 2007, 08:36 AM

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.

mathisfun1 · #6 $Old$ July 2nd, 2007, 10:18 AM

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.

mathisfun1 · #7 $Old$ July 2nd, 2007, 10:33 AM

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

ThePerfectHacker · #8 $Old$ July 9th, 2007, 02:28 PM

Quote:

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.

Quote:

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.

Isomorphism · #9 $Old$ December 29th, 2007, 06:06 AM

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!