Задача 98105

Темы:    [ Отношение порядка ] [ Деревья ] [ Принцип крайнего (прочее) ] [ Оценка + пример ]

Сложность: 3 Классы: 7,8

Условие

Автор: Толпыго А.К.

В некотором королевстве было 32 рыцаря. Некоторые из них были вассалами других (вассал может иметь только одного сюзерена, причём сюзерен всегда богаче своего вассала). Рыцарь, имевший не менее четырёх вассалов, носил титул барона. Какое наибольшее число баронов могло быть при этих условиях?
(В королевстве действовал закон: "вассал моего вассала – не мой вассал".)

Решение

  Оценка. У 8 баронов должно быть 32 вассала, а самый богатый рыцарь не может быть ничьим вассалом.
  Пример. Пусть 24 рыцаря – вассалы шести баронов, а все эти бароны – вассалы самого богатого Барона. Итого 7 баронов.

Ответ

7 баронов.

Замечания

4 балла

Источники и прецеденты использования

олимпиада
Название	Турнир городов
Турнир
Дата	1991/1992
Номер	13
вариант
Вариант	осенний тур, основной вариант, 8-9 класс
Задача
Номер	1