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

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

Задача 1#125503

Дано 8  различных натуральных чисел, не больших 15.  Докажите, что среди их положительных попарных разностей есть три одинаковых.

Показать доказательство

Так как все числа натуральные и не превышают 15,  то их попарные положительные разности принимают значения от 1  до 14.  Всего попарных разностей у 8  чисел 8⋅7
2 = 28  штук.

Заметим, что разность 14  имеется не более, чем у одной пары: такое возможно только при наличии чисел 1  и 15.  Тогда не менее   27  попарных разностей принимают значения от 1  до 13.

Воспользуемся принципом Дирихле: клетками будем считать числа от 1  до 13,  а кроликами — 27  попарных разностей. Если бы в каждой клетке сидело бы не больше двух кроликов, то всего кроликов было бы не более 13⋅2= 26< 27.  Значит, в какой-то клетке сидит хотя бы 3  кролика, что означает, что какое-то значение для разности принимается не менее трёх раз.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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