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.