1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

    VietDao29

    User Avatar
    Homework Helper

    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,
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?