Регион 2022
Готовиться с нами - ЛЕГКО!
Ошибка.
Попробуйте повторить позже
У Васи есть 
конфет нескольких сортов, где 
Известно, что если из данных 
конфет выбрать любую группу,
содержащую не менее 145 конфет (в частности, можно выбрать группу из всех данных 
конфет), то существует такой
сорт конфет, что выбранная группа содержит в точности 10 конфет этого сорта. Найдите наибольшее возможное значение
Источники:
Подсказка 1:
Пусть имеется n конфет. Рассмотрим все сорта конфет, для каждого из которых в наборе есть ровно 10 конфет этого сорта. Пусть их k. Очевидно, что какой-то из них является тем самым сортом из условия задачи.
Подсказка 2:
Подумайте, как можно нарушить выполнимость условия.
Подсказка 3:
Уберем по 1 конфете каждого из k сортов. Для оставшегося набора из n – k конфет условие не выполняется. Попробуйте оценить величину n – k.
Подсказка 4:
Очевидно, что n ≥ 10k, откуда n/10 ≥ k. Следовательно, n – k ≥ 9n/10. Как мы поняли ранее, этот набор не удовлетворяет условию. Значит, в нём менее 145 конфет. Теперь можно сделать оценку. Не забудьте придумать пример.
Оценка. Докажем, что 
«не работает».
Пусть дан набор из 
конфет. Назовём сорт критическим, если конфет этого сорта ровно 10 (среди всех данных 
конфет). Пусть у
нас 
критических сортов, тогда всего конфет не менее 
Уберём по одной конфете каждого критического сорта и
организуем группу из оставшихся 
конфет. Для этой группы нет сорта, представленного ровно 10 конфетами. Кроме
того,
Значит, в рассматриваемой группе не менее 145 конфет, поэтому условие задачи не выполняется.
Пример. Теперь приведём пример ситуации, в которой у Васи может быть 160 конфет. Пусть у него есть ровно по 10 конфет 16 сортов.
Пусть выбрана группа, для которой нет сорта, представленного ровно 10 конфетами. Тогда в эту группу не входит хотя бы одна конфета
каждого сорта (иначе говоря, ни один сорт не будет взят полностью), т.е. группа содержит не более 
конфет, значит, условие
задачи выполнено.
160
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
