# Homework Help: Student at School

1. Jan 2, 2005

### Pandaren

There are 1001 student at a certain school. Prove that at least one of them must have an even number of friends among the other 1000 students. (You should assume that friendship is symmetric so that if A is a friend of B, then B is a friend of A.)

Can anyone help me on this problem? Thanks

2. Jan 2, 2005

### hypermorphism

I'm assuming that you're counting zero as an even number. Have you tried proof by contradiction ? It seems to be the easiest approach.

3. Jan 3, 2005

### VietDao29

Hi,
Here's my suggestion:
A is B's friend, so B is A's friend. So the friendships in this case are 2.
Continue with A is C's friend, and C is A's friend
...
And because of that, the friendships in the whole school is an even or an odd number?
What if all the students in school have an odd number of friends?
odd number + odd number + ... + odd number (1001 times). So how many friendship in school if you calculate this way? Is it an even or an odd number?
---------------
And therefore, this exercise can be expanded like : prove that in the school has 2n + 1 (n is natural number) students, at least one of them has an even number of friends.
Hope this help,