Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Student at School

  1. Jan 2, 2005 #1
    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 :smile:
  2. jcsd
  3. Jan 2, 2005 #2
    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.
  4. Jan 3, 2005 #3


    User Avatar
    Homework Helper

    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,
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook