Вспоминай формулы по каждой теме
Решай новые задачи каждый день
Вдумчиво разбирай решения
ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!
Подтемы раздела закл (финал) 10 класс
Решаем задачу:

Ошибка.
Попробуйте повторить позже

Задача 1#128212

В программу соревнования входит 25 видов спорта, в каждом из которых определяется один победитель, получающий золотую медаль. В соревновании участвуют 25 спортсменов, каждый — во всех 25 видах спорта. Имеется 25 экспертов, каждый из которых должен сделать прогноз, сколько золотых медалей получит каждый спортсмен, при этом в его прогнозе количества медалей должны являться целыми неотрицательными числами с суммой 25. Эксперта признают компетентным, если он верно угадает количество золотых медалей хотя бы у одного спортсмена. При каком наибольшем k  эксперты могут сделать такие прогнозы, что хотя бы k  из них будут признаны компетентными независимо от исхода соревнования?

Источники: ВСОШ, ЗЭ, 2025, 10.7 (см. olympiads.mccme.ru)

Показать ответ и решение

Оценка. Покажем, что k≤ 24,  то есть, что любой эксперт может оказаться некомпетентным. Если этот эксперт считает, что все спортсмены возьмут по одной медали, опровергнем его результатом (25,0,0,...,0).  Иначе эксперт считает, что несколько (хотя бы один) спортсменов получат 0 медалей. Тогда распределим все медали между этими спортсменами так, чтобы каждый из них получил хотя бы одну медаль. В таком случае эксперт не угадает ни одного количества медалей.

Пример. Пусть прогноз одного эксперта — (1,1,1,...,1),  а прогнозы остальных — (1, 0, …, 0, 24), (0, 1, …, 0, 24), …, (0, 0, …, 1, 24) (на последнем месте 24, и ещё одна единица).

Если некомпетентным оказался первый эксперт, то в исходе точно есть хотя бы три нуля, иначе хотя бы в 23 позициях количество медалей не меньше 2, и тогда общее количество медалей не меньше 23⋅2> 30  — противоречие. Но тогда каждый из остальных экспертов компетентный.

Предположим теперь, что двое экспертов, отличных от первого, оказались некомпетентными. Тогда в двух позициях их прогнозы — 0 и 1 медалей, а значит, в реальном исходе в этих позициях не менее 2 медалей. Кроме того, ещё в 22 позициях прогнозы обоих экспертов — нули, значит, в реальном исходе в этих позициях не менее 1 медали. Тогда общее количество медалей не меньше 2⋅2+ 22⋅1> 25  — противоречие.

Ответ:

24

Специальные программы

Все специальные программы

Программа
лояльности v2.0

Приглашай друзей в Школково и получай вознаграждение до 10%!

Крути рулетку
и выигрывай призы!

Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.

Бесплатное онлайн-обучение

Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.

Налоговые вычеты

Узнай, как получить налоговый вычет при оплате обучения в «Школково».

Специальное предложение
для учителей

Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!

Вернём деньги за курс
за твою сотку на ЕГЭ

Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!

cyberpunkMouse
cyberpunkMouse
Рулетка
Вы можете получить скидку в рулетке!