Комбинаторика на ММО: графы, турниры, логика, конструктивы
Готовиться с нами - ЛЕГКО!
Ошибка.
Попробуйте повторить позже
Можно ли разбить множество целых чисел на три подмножества так, чтобы для любого целого значения 
числа 
принадлежали трём разным подмножествам?
Подсказка 1
Пойдем от противного: предположим, что такое разбиение существует. Будем писать m ∼ k, если целые числа m и k принадлежат одному и тому же подмножеству, и m ≭ k в противном случае. Что бы нам хотелось доказать?
Подсказка 2
Может, стоит доказать, что n эквивалентно каким-то "приятным" числам?
Подсказка 3
Что, если n ∼ n + 1937 и n ∼ n - 150?
Подсказка 4
Мы получим, что 0 ∼ -50.
Подсказка 5
Назовём тройку чисел представительной, если она содержит по одному числу от каждого подмножества разбиения. Попробуйте рассмотреть несколько представительных троек.
Подсказка 6
Например, можно рассмотреть {n-50; n; n+1987}, {n-100; n-50; n+1937}, {n+1937; n+1987; n+2⋅1987}.
Подсказка 7
Из первой тройки, например, следует, что n ≭ n-50 и n ≭ n+1987.
Докажем от противного, что нельзя. Предположим, что указанное в условии разбиение существует. Будем писать 
если целые числа
и 
принадлежат одному и тому же подмножеству, и 
в противном случае. Докажем, что для любого целого
отсюда будет следовать:
т.е. 
что противоречит условию задачи.
Назовём тройку чисел представительной, если она содержит по одному числу от каждого подмножества разбиения. По предположению тройки:
являются представительными при любом 
(заметим, что 
). Из второй и третьей тройки следует,
что:
а из первой тройки:
Отсюда вытекает первое утверждение: 
Теперь рассмотрим тройку 
которая также представительна.
Подставляя 
вместо 
получим представительную тройку 
Сравнение этих троек приводит ко второму
утверждению: 
Нельзя
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
