|
emily chung wrote: |
| i think you can use MI to prove, it seems it is true for all cases that if the number of students is odd. it is easy to see if n( number of students of school)=1 is true, also n=3 is true. then you assume n=2m+1 is true, you only need to consider the case of n=2m+2 and n=2m+3, you can find there should be at least one of the students has even number of firends when n = 2m+3. i am not sure is this method can apply, but it seems it is work
let me post another question here, it is quite interest. Show that in any group of two or more persons there are at least two having the same number of friends (the friendship relation is symmetric) |
Let be the number of persons in that group. Then the number of friends can only be 0,1,…,(n-1). We divide it into 2 cases. (1) If a person has n-1 friends, then none of the remaining n-1 persons has 0 friend, since that person is friend with all of them. Thus the number of friend can only be 1,2,…,(n-1). By piegonhole principle, at least 2 of them have the same number of friends.
(2) If no persons have n-1 friends. Then the number of friends can only be 0,1,…,(n-2). Again, by piegonhole principle, at least 2 of them have the same number of friends, so we are done.