ES242. Data Structures and Algorithms I. Quiz 03
ES242. Data Structures and Algorithms I.
Quiz 03
Issued: 19 Jan, 2023
Problem 1. Party Puzzle I
The following is true for n guests at a party:
- In any group of three guests, there are two guests who do not know each other, and
- In any group of seven guests, there are two guests who do know each other.
At the end of the party, everyone gives a present to all the guests he or she knows.
The total number of gifts given is at most:
- 6n
- 4n
- 3n
- None of the above
Problem 2. Party Puzzle II
Is it possible that there is a group of six people where there is no group of three guests who are mutual friends and there is no group of three guests who are mutual strangers?
- Yes
- No
Assume that every pair of people are either mutual friends or mutual strangers.
Problem 3. Party Puzzle III
Is it possible that there is a group of five people where there is no group of three guests who are mutual friends and there is no group of three guests who are mutual strangers?
- Yes
- No
Assume that every pair of people are either mutual friends or mutual strangers.