ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 116942
Темы:    [ Теория множеств (прочее) ]
[ Доказательство от противного ]
Сложность: 4+
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

Можно ли множество всех натуральных чисел разбить на непересекающиеся конечные подмножества  A1, A2, A3, ...  так, чтобы при любом натуральном k сумма всех чисел, входящих в подмножество Ak, равнялась  k + 2013?


Решение

  Предположим, что искомое разбиение существует. Назовём множество Ak большим, если оно содержит больше одного элемента.   Предположим, что число больших множеств конечно. Тогда найдётся такой номер  t > 1,  что каждое из множеств  At, At+1, At+2, ...  состоит из одного элемента. Итак, объединение множеств  At, At+1, At+2, ...  есть множество  {t + 2013, t + 2014, ...}.  Значит, объединение множеств  A1, A2, ..., At–1  совпадает с множеством  {1, 2, ..., t + 2012}.  Но сумма элементов в этих множествах равна  2014 + 2015 + ... + (t + 2012),  что меньше суммы элементов множества  {1, 2, ..., t + 2012}.  Противоречие. Следовательно, больших множеств бесконечно много.
  Сумма чисел каждого из множеств  A1, A2, ..., An  не превосходит  n + 2013,  значит, все их элементы лежат в множестве  {1, 2, ..., n + 2013}.  С другой стороны, так как имеется бесконечно много больших множеств, то найдётся такой номер n, что среди множеств  A1, A2, ..., An  хотя бы 2014 больших. Тогда объединение всех множеств  A1, A2, ..., An  содержит не менее  n + 2014  элементов. Противоречие.


Ответ

Нельзя.

Источники и прецеденты использования

олимпиада
Название Всероссийская олимпиада по математике
год
Год 2012-2013
этап
1
Вариант 4
класс
Класс 10
Задача
Номер 10.4
олимпиада
Название Всероссийская олимпиада по математике
год
Год 2012-2013
этап
1
Вариант 4
класс
Класс 11
Задача
Номер 11.3

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .