Базовый вариант весеннего тура Турнира Городов
Ошибка.
Попробуйте повторить позже
2003 доллара разложили по кошелькам, а кошельки разложили по карманам. Известно, что всего кошельков больше, чем долларов в любом кармане. Верно ли, что карманов больше, чем долларов в каком-нибудь кошельке? (Класть кошельки один в другой не разрешается.)
Источники:
Подсказка 1!
1) Много условий зависимостей. Давайте обозначим количество карманов и количество кошельков за x и y, и попробуем как-то оценить количество долларов...
Подсказка 2!
2) Отлично, но теперь давайте посмотрим на утвердение в задаче, как часто доказываются задачи про дирихле, каким методом?
Подсказка 3!
3) От противного, и правда! Осталось аккуратно довести решение, идейно мы задачу уже решили.
Пусть карманов — , а кошельков —
. Тогда по условию в каждом кармане меньше
долларов.Значит, всего долларов меньше, чем
(пересчитали доллары по всем карманам). Если утверждение “карманов больше, чем долларов в каком-нибудь кошельке” неверно, то верно,
что “карманов не больше, чем долларов в любом кошельке”, то есть в каждом кошельке хотя бы
долларов. Тогда всего денег, с одной
стороны, хотя бы
, так как в каждом из
кошельков хотя бы
долларов. А с другой стороны мы поняли, что всего долларов меньше
. Противоречие.
да
Специальные программы

Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!

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

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

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

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

Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!