Register

pigeonhole

• retagged by
4,098 views
1 votes
1 votes
Show that in a group of 10 people (where any two people are either friends or enemies), there are either three mutual friends or four mutual enemies, and there are either three mutual enemies or four mutual friends.
• retagged by
User Avatar

1 Answer

Best answer
4 votes
4 votes
Take a single person A out of the 10 people. The remaining 9 people has to be either friends or enemy with A. Therefore acc to pigeon hole principle there atleast⎾9/2⏋(i.e., 5) friends or enemy of A. Lets assume that A has five friends.Now, if at least two of these are friends then there are three mutual friends if not then there are five mutual enemies(which also implies that there are four mutual enemies). similarly we can prove that there are either three mutual enemies or four mutual friends by assuming A has 5 enemies.
• selected by
User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
1 answer
1
aditi19 asked Oct 25, 2018
978 views
Rosen-Pigeonhole Principle
How many cards must be chosen from a standard deck of 52 cards to guarantee that there are at least two cards of each of two different kinds? what this question means?
How many cards must be chosen from a standard deck of 52 cards to guarantee that there are at least two cards of each of two different kinds?what this question means?
User Avatar
1 votes
1 votes
1 answer
2
Sammohan Ganguly asked May 25, 2018
1,363 views
Pigeonhole Principle (2)
Suppose a graph $G$ has $6$ nodes. Prove that either $G$ or $G'$ must contain a triangle. ($G'$ is the complement of $G$.) Prove it using pigeonhole principle.
Suppose a graph $G$ has $6$ nodes. Prove that either $G$ or $G'$ must contain a triangle.($G'$ is the complement of $G$.) Prove it using pigeonhole principle.
User Avatar
4 votes
4 votes
2 answers
3
sourav. asked Aug 24, 2016
2,179 views
generalised pigeonhole principle
Show that if seven integers are selected from the first 10 positive integers, there must be at least two pairs of these integers with the sum 11. Attempt-:partition will be {(1,10),(2,9),(3,8)(4,7)(5,6)} now how to apply pigeonhole principle to find the answer?
Show that if seven integers are selected from the first10 positive integers, there must be at least two pairsof these integers with the sum 11.Attempt-:partition will be ...
User Avatar
2 votes
2 votes
2 answers
4
Anu asked Jul 14, 2015
2,000 views
pigeonhole
Prove that at a party where there are at least two people, there are two people who know the same number of other people there.
Prove that at a party where there are at least two people, there are two people who know the same number of other people there.
User Avatar
Link Copied!