Условие
Два подмножества множества натуральных чисел называют конгруэнтными, если одно получается из другого сдвигом на целое число.
(Например, множества чётных и нечётных чисел конгруэнтны.) Можно ли разбить множество натуральных чисел на бесконечное число
(не пересекающих друг друга) бесконечных конгруэнтных подмножеств?
Решение
Покажем, как построить требуемое разбиение. Разбиение однозначно задается функцией
f:N
N
на множестве
N натуральных чисел, сопоставляющей натуральному числу номер множества,
которому оно принадлежит. Определим функцию
f на отрезке
[2
k-1
+1
;2
k]
индуктивно
по следующим правилам:
1)
f(1)
=1
.
2) Пусть
f(
x)
уже определено для всех
x
2
k-1
, а
y
[2
k-1
+1
;2
k]
.
Тогда положим
f(
y)
=f(
y-2
k-1)
при
k четном и
f(
y)
=f(
y-2
k-1)
+2
s при
k=2
s+1
нечетном.
Легко проверить, что эта функция
f задает требуемое разбиение.
Ответ
Ответ
Можно.
Источники и прецеденты использования
