ВсОШ 2026, 7 класс, задача 8
( баллов) Царство гномов состоит из кланов по гномов. Каждый гном входит только в один клан.
Гном считается высоким, если найдется хотя бы кланов, не включая его собственный, средний рост в каждом из которых меньше, чем рост этого гнома.
Какое наибольшее количество высоких гномов может быть в царстве?
Ответ
Ответ: .
Решение. Посчитаем средний рост гномов в каждом клане и отсортируем кланы по возрастанию среднего роста . Рассмотрим самого низкого гнома в каждом из первых кланов. Его рост не больше, чем средний в его клане, а поскольку его клан входит в кланов с меньшим средним ростом, то этот гном не может быть высоким. Значит, гномов, которых нельзя назвать высокими, не менее .
Теперь построим пример, когда таких гномов всего , а все остальные высокие. Пусть в первых кланах будет гном роста см, а остальные — роста см. Тогда средний рост в этих кланах будет равен см. В оставшихся кланах пусть будут все гномы ростом см. Тогда в каждом из первых кланов все гномы, кроме одного, будут высокими, а в оставшихся кланах все гномы будут высокими.
Верное решение.