Math Help Forum - View Single Post

ThePerfectHacker · #8 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.