Два подмножества множества натуральных чисел назовем конгруэнтными, если одно получается из другого сдвигом на целое число. (Например, множества четных и нечетных чисел конгруэнтны.) Можно ли разбить множество натуральных чисел на бесконечное число (непересекающихся) бесконечных конгруэнтных подмножеств?
Ответ
Предположим, что задача уже решена. Пусть $A$ — то из множеств разбиения, которое содержит единицу. Остальные множествa разбиения получаются из $A$ сдвигами на некоторые натуральные числа, множество которых, дополненное нулем, мы обозначим через $B$. Пусть для каждого $b\in B$ множество $A_{b}$ — результат сдвига множества $A$ на $b,$ то есть множество всех чисел вида $a+b,$ где $a\in A$. По условию, если $b_{1}\neq b_{2},$ то $A_{b_{1}}\cap A_{b_{2}}=\oslash$ и всякое натуральное число $n$ принадлежит одному из множеств $A_{b},$ то есть каждое натуральное число единственным образом представляется в виде суммы $n=a+b$.
Построение множеств $A$ и $B$ мы осуществим двумя способами.
Первый способ. Пусть множества $A$ и $B$. обладающие свойством $n=a+b$ построены. Поставим в соответствие каждому натуральному числу $n=a+b$ точку плоскости $Oxy$ с координатами $\left ( a;b \right )$.
- Пусть $M$ — множество всех полученных точек плоскости. Множество $M,$ очевидно, обладает следующими свойствами:
- если $A$ — проекция множества $M$ на ось $Ox,$ а $B$ — проекция $M$ на ось $O,y$ то множество $M$ совпадает со всем множеством пар $\left ( a;b \right )$.
- пересечение множества $M$ с каждой прямой $x+y=n$ состоит из единственной точки: в частности, при $n=1$ — это точка $\left ( 1;0 \right )$.
Ясно, что, построив хотя бы одно множество $M$ обладающее свойствами 1) и 2), мы получим нужное разбиение множества натуральных чисел.
Множество $M$ построим как объединение множеств $M_{0}\subset M_{1}\subset M_{2}\subset …\subset M_{n}\subset \ldots,$ которые, в свою очередь, будем строить так:
Пусть $M_{0}=\left \{ \left ( 1;0 \right ) \right \}$. Назовем $n$-ой диагональю прямую $x+y=n$. Точка $\left ( 1;0 \right )$ попадает на первую диагональ: вычеркнем ее и в дальнейшем, строя множества $M_{1}$ будем последовательно вычеркивать диагонали, на которые попадают построенные точки.
Сдвинем множество $M_{0}$ на единицу вправо и положим $M_{1} = \left \{ \left ( 1;0 \right ), \left ( 2;0 \right ) \right \}$ при этом вычеркнем вторую диагональ(Рис.1). Затем сдвинем множество $M_{1}$ на две единицы вверх и присоединим полученные точки к $M_{1}$: это будет множество $M_{2}$: при этом вычеркнем третью и четвертую диагонали.
Множество $M_{2}$ сдвинем на четыре единицы вправо — так, чтобы вычеркнуть следующие четыре диагонали: получим множество $M_{3}$
Вообще. множество $M_{k+1}$ строим так: сдвигаем множество $M_{k}$ на $2^{k}$ единиц вправо или вверх — так, чтобы вычеркнуть диагонали с номерами $2^{k} + 1, 2^{k} + 2, 2^{k+1}$.
Легко видеть, что объединение множеств $M_{0}, M_{1},\ldots M_{n}\ldots$ обладает свойствами 1) и 2).
Второй способ. Как известно всякое натуральное число $n$ представляется в виде $$n=a_{0}\cdot 2^{k}+a_{1}\cdot 2^{k-1}+\ldots+a_{k-1}\cdot 2+a_{k},$$ где $a_{i}$ равно 0 или 1. причем такое представление единственно. На этом основана двоичная запись числа $n$: $n_{2} = \overline{a_{0}a_{1}\ldots a_{k-1}a_{k}}$
Рассмотрим теперь два множества натуральных чисел: множество $A,$ состоящее из чисел, в двоичной записи которых единица находится в нечетных разрядах, и множество $B$ состоящее из 0 и чисел, в двоичной записи которых единица находится в четных разрядах.
Очевидно, любое натуральное $n$ единственным образом представляется в виде суммы $n=a+b$.
Множества $A$ и $B$ обладают свойством $n=a+b$. и поэтому множества $A_{b}$ дают нужное разбиение.
