...

falcon handsome moderators

09/03/2017 at 10:48
Answers
3
Follow

Each member of a club has at most three enemies in the club. (Here enemies are mutual). Show that the members can be divided into two so that each member in each member in each group has at most one enemy in the group


games

    List of answers
  • ...
    Ace Legona 09/03/2017 at 20:09

     In the beginning, randomly divide the members into two groups. Let S be the sum of the number of the pairs of enemies in each group. If a member has at least two enemies in the same group, then the member has at most one enemy in the other group. Transferring the member to the other group, we will decrease S by at least one. Since S is a nonnegative integer, it cannot be decreased forever. So after finitely many transfers, each member can have at most one enemy in the same group. 

  • ...
    Faded 22/01/2018 at 12:19

    In the beginning, randomly divide the members into two groups. Let S be the sum of the number of the pairs of enemies in each group. If a member has at least two enemies in the same group, then the member has at most one enemy in the other group. Transferring the member to the other group, we will decrease S by at least one. Since S is a nonnegative integer, it cannot be decreased forever. So after finitely many transfers, each member can have at most one enemy in the same group.

  • ...
    Vũ Việt Vương 01/04/2017 at 16:55

    n the beginning, randomly divide the members into two groups. Let S be the sum of the number of the pairs of enemies in each group. If a member has at least two enemies in the same group, then the member has at most one enemy in the other group. Transferring the member to the other group, we will decrease S by at least one. Since S is a nonnegative integer, it cannot be decreased forever. So after finitely many transfers, each member can have at most one enemy in the same group. 



Weekly ranking