Friends or non-friends: Difference between revisions
Jump to navigation
Jump to search
Oscarlevin (talk | contribs) No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
If there are six people in a room, must there be at least three of them who are either all friends with each other or all non-friends with each other? (If A is friends with B, then B is friends with A.) Explain. | If there are six people in a room, must there be at least three of them who are either all friends with each other or all non-friends with each other? (If A is friends with B, then B is friends with A.) Explain. | ||
{{Solution| Arbitrarily choose one of the six people and label him/her A. For each of the remaining five people A is either a friend or he is not. If A is a friend then draw a black line between A and that person, and if he is not then draw a white line. We get 5 distinct lines connecting A to the other people in the room, and so by the pigeonhole principle 3 of them must be the same color. With no loss of generality we may assume 3 of them are black. Denote the other ends of these lines B,C,D. This gives an additional 3 lines BC, BD,CD. If even one of these lines is black then we can form a black triangle with A, which means there are 3 people at the party who are all friends. Otherwise the lines BC,BD,CD are all white and thus the triangle BCD is white, giving a group for which no one knows each other.}} | |||
[[Category: Graph theory]] | [[Category: Graph theory]] | ||
[[Category: Pigeonhole principle]] | [[Category: Pigeonhole principle]] | ||
Revision as of 17:38, 7 November 2010
If there are six people in a room, must there be at least three of them who are either all friends with each other or all non-friends with each other? (If A is friends with B, then B is friends with A.) Explain.
Solution
Arbitrarily choose one of the six people and label him/her A. For each of the remaining five people A is either a friend or he is not. If A is a friend then draw a black line between A and that person, and if he is not then draw a white line. We get 5 distinct lines connecting A to the other people in the room, and so by the pigeonhole principle 3 of them must be the same color. With no loss of generality we may assume 3 of them are black. Denote the other ends of these lines B,C,D. This gives an additional 3 lines BC, BD,CD. If even one of these lines is black then we can form a black triangle with A, which means there are 3 people at the party who are all friends. Otherwise the lines BC,BD,CD are all white and thus the triangle BCD is white, giving a group for which no one knows each other.