Theorem: In any group of n >= 2 people there are at least two people who have th
ID: 3195907 • Letter: T
Question
Theorem: In any group of n >= 2 people there are at least two people who have the same number of friends
within the group.
Example: Consider ve people A;B;C;D;E where the pairs of friends are:
A and B, A and C, B and C, B and D, B and E, and C and E
So, A has 2 friends, B has 4 friends, C has 3 friends, D has 1 friend, and E has 2 friends.
Therefore A and E have the same number of friends.
Answer the questions below, and eventually write a proof (by contradiction - you can combine it with a proof by
cases) for the theorem.
(Note that in this problem we are only counting friends within the group.)
(1 point) (a) What is the minimum number of friends a member of this group can have?
(1 point) (b) What is the maximum number of friends a member of this group can have?
(1 point) (c) How many di erent integer values are there between the minimum (found in (a)) and maximum
(found in (b)) including the minimum and maximum values?
(1 point) (d) What is the maximum possible value for the number of friends of any member if it is known that a
certain member of this group has no friends?
(4 point) (e) Now write a proof by contradiction (you may combine it with proof by cases) for the theorem. Start
as follows: "Consider a group of n >= 2 people. Suppose that it is not true that at least two people in this group
have the same number of friends." Finish this proof making use of parts (a)-(d).
Explanation / Answer
(a) 0
Suppose A is friend with B and C. B is friend with A and D. C is friend with A and Delhi than E doesn't have any friends.
(b) 4
AB,AC,AD,AE,BD,CE
(c) 5
(d) 3
AB,AC,AD,BD,CB
(e) AB, AC, AD, BC, BD
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.