Два подмножества множества натуральных чисел назовем конгруэнтными, если одно получается из другого сдвигом на целое число. (Например, множества четных и нечетных чисел конгруэнтны.) Можно ли разбить множество натуральных чисел на бесконечное число (непересекающихся) бесконечных конгруэнтных подмножеств?
Ответ
Предположим, что задача уже решена. Пусть A — то из множеств разбиения, которое содержит единицу. Остальные множествa разбиения получаются из A сдвигами на некоторые натуральные числа, множество которых, дополненное нулем, мы обозначим через B. Пусть для каждого b∈B множество Ab — результат сдвига множества A на b, то есть множество всех чисел вида a+b, где a∈A. По условию, если b1≠b2, то Ab1∩Ab2=⊘ и всякое натуральное число n принадлежит одному из множеств Ab, то есть каждое натуральное число единственным образом представляется в виде суммы n=a+b.
Построение множеств A и B мы осуществим двумя способами.
Первый способ. Пусть множества A и B. обладающие свойством n=a+b построены. Поставим в соответствие каждому натуральному числу n=a+b точку плоскости Oxy с координатами (a;b).
- Пусть M — множество всех полученных точек плоскости. Множество M, очевидно, обладает следующими свойствами:
- если A — проекция множества M на ось Ox, а B — проекция M на ось O,y то множество M совпадает со всем множеством пар (a;b).
- пересечение множества M с каждой прямой x+y=n состоит из единственной точки: в частности, при n=1 — это точка (1;0).
Ясно, что, построив хотя бы одно множество M обладающее свойствами 1) и 2), мы получим нужное разбиение множества натуральных чисел.
Множество M построим как объединение множеств M0⊂M1⊂M2⊂…⊂Mn⊂…, которые, в свою очередь, будем строить так:
Пусть M0={(1;0)}. Назовем n-ой диагональю прямую x+y=n. Точка (1;0) попадает на первую диагональ: вычеркнем ее и в дальнейшем, строя множества M1 будем последовательно вычеркивать диагонали, на которые попадают построенные точки.
Сдвинем множество M0 на единицу вправо и положим M1={(1;0),(2;0)} при этом вычеркнем вторую диагональ(Рис.1). Затем сдвинем множество M1 на две единицы вверх и присоединим полученные точки к M1: это будет множество M2: при этом вычеркнем третью и четвертую диагонали.
Множество M2 сдвинем на четыре единицы вправо — так, чтобы вычеркнуть следующие четыре диагонали: получим множество M3
Вообще. множество Mk+1 строим так: сдвигаем множество Mk на 2k единиц вправо или вверх — так, чтобы вычеркнуть диагонали с номерами 2k+1,2k+2,2k+1.
Легко видеть, что объединение множеств M0,M1,…Mn… обладает свойствами 1) и 2).
Второй способ. Как известно всякое натуральное число n представляется в виде n=a0⋅2k+a1⋅2k−1+…+ak−1⋅2+ak,
Рассмотрим теперь два множества натуральных чисел: множество A, состоящее из чисел, в двоичной записи которых единица находится в нечетных разрядах, и множество B состоящее из 0 и чисел, в двоичной записи которых единица находится в четных разрядах.
Очевидно, любое натуральное n единственным образом представляется в виде суммы n=a+b.
Множества A и B обладают свойством n=a+b. и поэтому множества Ab дают нужное разбиение.