What is a Graph? · Connected Components

Lesson 1

Nikolai Chukhin · Alexander S. Kulikov

Problem. There are \(n\) stones of different weights. An expert knows the weights and wants to convince the court that a particular stone is the heaviest one. For this, she repeatedly uses a pan balance to compare the weights of some two stones.

What is the minimum number of comparisons required?

5 points