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