ES242. Data Structures and Algorithms I. Quiz 03

ES242. Data Structures and Algorithms I.

Quiz 03

Issued: 19 Jan, 2023

Back to course page

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.