Friends or non-friends - Revision history

Vampire Library: /* Help */

2010-11-08T00:44:49Z

Help

← Older revision		Revision as of 18:44, 7 November 2010
Line 3:		Line 3:
	==Help==		==Help==

	{{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.}}		{{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 in which no one knows each other.}}

	[[Category: Graph theory]]		[[Category: Graph theory]]
	[[Category: Pigeonhole principle]]		[[Category: Pigeonhole principle]]

Vampire Library at 00:39, 8 November 2010

2010-11-08T00:39:15Z

← Older revision		Revision as of 18:39, 7 November 2010
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.

			==Help==

	{{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.}}		{{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.}}

Vampire Library at 00:38, 8 November 2010

2010-11-08T00:38:17Z

← Older revision		Revision as of 18:38, 7 November 2010
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]]

Oscarlevin at 14:43, 16 May 2010

2010-05-16T14:43:04Z

← Older revision		Revision as of 08:43, 16 May 2010
Line 1:		Line 1:
	~~==Puzzle==~~

	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.

	[[Category: Graph theory]]		[[Category: Graph theory]]
	[[Category: Pigeonhole principle]]		[[Category: Pigeonhole principle]]

Oscarlevin at 13:10, 14 May 2010

2010-05-14T13:10:56Z

← Older revision		Revision as of 07:10, 14 May 2010
Line 4:		Line 4:

	[[Category: Graph theory]]		[[Category: Graph theory]]
	[[Category: Pigeonhole ~~theorem~~]]		[[Category: Pigeonhole principle]]

Oscarlevin: Created page with '==Puzzle== 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 frien…'

2010-03-30T20:07:02Z

Created page with '==Puzzle== 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 frien…'

New page

==Puzzle==

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.

[[Category: Graph theory]]
[[Category: Pigeonhole theorem]]