Processing math: 100%

М685. О конгруэнтных подмножествах

Два подмножества множества натуральных чисел назовем конгруэнтными, если одно получается из другого сдвигом на целое число. (Например, множества четных и нечетных чисел конгруэнтны.) Можно ли разбить множество натуральных чисел на бесконечное число (непересекающихся) бесконечных конгруэнтных подмножеств?

Ответ

Предположим, что задача уже решена. Пусть A — то из множеств разбиения, которое содержит единицу. Остальные множествa разбиения получаются из A сдвигами на некоторые натуральные числа, множество которых, дополненное нулем, мы обозначим через B. Пусть для каждого bB множество Ab — результат сдвига множества A на b, то есть множество всех чисел вида a+b, где aA. По условию, если b1b2, то Ab1Ab2= и всякое натуральное число n принадлежит одному из множеств Ab, то есть каждое натуральное число единственным образом представляется в виде суммы n=a+b.

Построение множеств A и B мы осуществим двумя способами.

Первый способ. Пусть множества A и B. обладающие свойством n=a+b построены. Поставим в соответствие каждому натуральному числу n=a+b точку плоскости Oxy с координатами (a;b).

    Пусть M — множество всех полученных точек плоскости. Множество M, очевидно, обладает следующими свойствами:

  1. если A — проекция множества M на ось Ox, а B — проекция M на ось O,y то множество M совпадает со всем множеством пар (a;b).
  2. пересечение множества M с каждой прямой x+y=n состоит из единственной точки: в частности, при n=1 — это точка (1;0).

Ясно, что, построив хотя бы одно множество M обладающее свойствами 1) и 2), мы получим нужное разбиение множества натуральных чисел.

Множество M построим как объединение множеств M0M1M2Mn, которые, в свою очередь, будем строить так:

Пусть M0={(1;0)}. Назовем n-ой диагональю прямую x+y=n. Точка (1;0) попадает на первую диагональ: вычеркнем ее и в дальнейшем, строя множества M1 будем последовательно вычеркивать диагонали, на которые попадают построенные точки.

Сдвинем множество M0 на единицу вправо и положим M1={(1;0),(2;0)} при этом вычеркнем вторую диагональ(Рис.1). Затем сдвинем множество M1 на две единицы вверх и присоединим полученные точки к M1: это будет множество M2: при этом вычеркнем третью и четвертую диагонали.

144
144

Множество M2 сдвинем на четыре единицы вправо — так, чтобы вычеркнуть следующие четыре диагонали: получим множество M3

144
144

Вообще. множество Mk+1 строим так: сдвигаем множество Mk на 2k единиц вправо или вверх — так, чтобы вычеркнуть диагонали с номерами 2k+1,2k+2,2k+1.

Легко видеть, что объединение множеств M0,M1,Mn обладает свойствами 1) и 2).

Второй способ. Как известно всякое натуральное число n представляется в виде n=a02k+a12k1++ak12+ak,

где ai равно 0 или 1. причем такое представление единственно. На этом основана двоичная запись числа n: n2=¯a0a1ak1ak

Рассмотрим теперь два множества натуральных чисел: множество A, состоящее из чисел, в двоичной записи которых единица находится в нечетных разрядах, и множество B состоящее из 0 и чисел, в двоичной записи которых единица находится в четных разрядах.

Очевидно, любое натуральное n единственным образом представляется в виде суммы n=a+b.

Множества A и B обладают свойством n=a+b. и поэтому множества Ab дают нужное разбиение.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *