Олимпиадная задача по теории множеств: разбиение натуральных чисел для классов 8-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 элементов. Противоречие.
Обсуждение
0Комментариев пока нет.