Problem #PRU-98105

Problems Methods Examples and counterexamples. Constructive proofs Pigeonhole principle

Problem

In a certain kingdom there were 32 knights. Some of them were vassals of others (a vassal can have only one suzerain, and the suzerain is always richer than his vassal). A knight with at least four vassals is given the title of Baron. What is the largest number of barons that can exist under these conditions?

(In the kingdom the following law is enacted: “the vassal of my vassal is not my vassal”).