2014-06-08
Множество из $2^{n}$ элементов разбито на попарно непересекающиеся подмножества. Рассматривается операция, состоящая в переводе некоторых элементов из одного подмножества в другое, причем число переводимых элементов должно совпадать с числом элементов во втором множестве (которое должно содержать элементов не больше, чем первое). Доказать, что с помощью конечного числа таких операций можно получить подмножество, совпадающее с исходным множеством.
Решение:
Рассмотрим подмножества (если такие имеются), которые содержат нечетное количество элементов. Поскольку общее количество элементов четно, то количество множеств с нечетным числом элементов также четно. Разобьем эти множества на пары (произвольным образом). С множествами из каждой пары произведем операцию, указанную в условии задачи, т. е. из большего множества переведем в меньшее столько элементов, сколько содержит меньшее множество. После этого все множества будут содержать четное число элементов. Рассмотрим те множества, количество элементов в которых не делится на 4 (при $n \geq 2$, если же $n = 1$, то элементов всего 2 и оба они уже содержатся в одном подмножестве). Поскольку общее количество элементов делится на 4, то количество таких подмножеств четно. Разобьем эти множества на пары произвольным образом и над каждой парой произведем операцию, указанную в условии задачи. После этого количество элементов в каждом множестве будет делиться на 4. Аналогично поступаем далее так, чтобы количество элементов в каждом множестве делилось (последовательно) на $8, 16, \cdots$. Когда количество элементов в каждом множестве будет делиться на $2^{n}$, то все $2^{n}$ элементов будут содержаться в одном подмножестве.