Комбинаторика на Иннополисе
Ошибка.
Попробуйте повторить позже
Множество всех целых положительных чисел разбили на два непересекающихся подмножества — 
и 
. Докажите, что для любого
целого 
найдутся такие целые 
что 
или 
Источники:
Подсказка 1
Рассмотрите случай, когда одно из множеств (например, А) конечно. Пусть m — наибольший элемент А. Какие числа гарантированно попадут в В и удовлетворят условию?) Возьмите х = m+1, y = m+2, х+у = 2m+3 — все они обязаны лежать в B.
Подсказка 2
Если оба множества бесконечны, предположите противное: для некоторого n > 0 нужных троек нет. Как выбрать числа а > b > с > n из А, чтобы получить противоречие? Число b-с не может лежать ни в А иначе (b, b-с, с) с В, ни в В иначе (a+b, c+a, b-c) с B
Подсказка 3
Почему тройка (a+b, b+с, с+а) обязана полностью принадлежать В? Как это приводит к тому, что число b-с не принадлежит ни А, ни В? Это нарушает условие разбиения N на два непересекающихся множества!
Без ограничения общности, пусть множество 
содержит конечное число элементов, наибольший из которых равен 
Тогда
и условие задачи выполнено.
Теперь будем считать, что каждое из множеств 
содержит бесконечное число элементов. Препдположим, что существует такое
целое 
что для любых целых 
множество 
не содержится ни в 
ни в 
Выберем 
из
множества 
с условием 
по предположению, 
иначе 
что возможно, поскольку 
бесконечно.
Тогда 
иначе нарушается предположение, но тогда 
иначе 
Получили,
что число 
не содержится ни в 
ни в 
что противоречит условию. Таким образом, исходное утверждение
доказано.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
