Разбиение множеств

[wpoms.]

Для всех натуральных чисел `n` обозначим через `S_n` множество состоящее из первых `n` натуральных чисел, то есть `S_n = {1, 2, 3, 4, . . . , n - 1, n}`. (a) Для каких значений `n` возможно представить `S_n` как объединение двух не пустых, не содержащих общие элементы, множеств, суммы элементов которых равны друг другу? (b) Для каких значений `n` возможно представить `S_n` как объединение трех не пустых, не содержащих общие элементы, множеств, суммы элементов которых равны друг другу?

@темы: Теория чисел, Множества

Comments

[_ТошА_]

Кстати, интересно. Завтра обязательно посмотрю

[Adjirranirr]

Пусть `f : 2^{NN} -> NN` — функция, сопоставляющая подмножеству натуральных чисел его сумму.

(а) Из `f (S_n) = (n^2 + n)/2 = f(A) + f(B)` и `f(A) = f(B)` следует четность числа `(n^2 + n)/2`; тогда, `n = 4k` или `n = 4k - 1`, `k \in NN`.
Для `n = 4k` искомое разбиение `A = {1,\ 2,\ ...,\ k,\ 3k + 1,\ 3k + 2,\ ...,\ 4k},\ B = S_n \\ A`.
Для `n = 4k - 1`, искомое разбиение — `A = {1,\ 2,\ 4,\ 5,\ ...,\ k,\ k + 1,\ k + 2,\ 3k + 1,\ 3k + 2,\ ...,\ 4k - 1}`, `B = {3,\ k + 3,\ k + 4,\ ...,\ 2k,\ 2k + 1,\ ...,\ 3k}`. `f(B) = 3 + \sum_{i = k + 3}^{3k} i = 3 + f(S_{3k}) - f(S_{k + 2}) = 3 + \frac { 9k^2 + 3k - (k^2 + 5k + 6)} {2} = 3 + \frac {1} {2} (8k^2 - 2k - 6) = 4k^2 - k = \frac {f(S_n)} {2}`, а значит, `f(A) = f(B)`.

(b) Из `f(S_n) = f(A) + f(B) + f(C)` следует делимость числа `(n^2 + n)/2` на 3, и следовательно, `n = 3k`, `k \in NN`.
Если `k = 2p`, то искомое разбиение — `A = {1,\ 3,\ ...,\ 2p - 1,\ 4p + 2,\ 4p + 4,\ ...,\ 6p}`, `B = {2,\ 4,\ ...,\ 2p,\ 4p + 1,\ 4p + 3,\ ...,\ 6p - 1}`, `C = {2p + 1,\ 2p + 2,\ ...,\ 4p}`.
Пусть теперь `k = 2p - 1`, и пусть `A = {2p,\ 2p + 1,\ ...,\ 4p - 2}`, `B = {2,\ 4,\ ...,\ 2p - 2,\ 4p, 4p + 2, ..., 6p - 4}`, `C = {1,\ 3,\ ...,\ 2p - 1,\ 4p - 1,\ 4p + 1,\ ...,\ 6p - 3}`. Очевидно, `f(A) = f(S_{2k}) - f(S_k) = 1/2 (3k^2 + k) = 6p^2 - 5p + 1`, `f(B) = 2 f(S_{p-1}) + 2 (f(S_(3p - 2)) - f(2p - 1)) = 6p^2-8p+2`, `f(C) = 6p^2-2p`, и `1/2 (f(C) - f(B)) = 3p - 1`. Таким образом, поменяв местами во множествах `B` и `C` подмножества элементов `X` и `Y` соответственно, такие, что `f(Y) = f(X) + 3p - 1`, мы получим искомое разбиение. Если `p` четно, то, например, `X = {p + 2} \subset B`, `Y = {4p + 1} \subset C`. Если `p` нечетно, то, например, `X = {p - 3} \subset B`, `Y = {2p - 1,\ 2p - 3} \subset C`. Очевидно так же, что при `p = 1: S_n = S_{6p - 3} = S_3 = {1, 2, 3}`, и это множество разбить невозможно.
Окончательно — для (a): `n = 4k` или `n = 4k - 1`, для (b): `n = 3k,\ k > 1`.

[Adjirranirr]

Хм. Один случай не учел =)

[Adjirranirr]

Для (b), если `n = 3k - 1`,
при `k = 2p`, искомое разбиение `A = {2p,\ 2p+1,\ ...,\ 4p - 2, 6p - 1}`, `B = {1,\ 3,\ ..., 2p - 1,\ 4p,\ 4p + 2,\ ...,\ 6p - 2}`, `C = {2,\ 4,\ ...,\ 2p - 2,\ 4p - 1,\ 4p + 1,\ ...,\ 6p - 3}`.
при `k = 2p - 1`, пусть `A = {2p,\ 2p + 1,\ ...,\ 4p - 4, 6p - 4}`, `B = {1,\ 3,\ ..., 2p - 1,\ 4p - 3,\ 4p - 1,\ 4p + 1,\ ...,\ 6p - 5}` и `C = {2,\ 4,\ ...,\ 2p - 2,\ 4p-2,\ 4p,\ 4p + 2,\ ...,\ 6p - 6}`. Тогда `f(A) = 1/3 f(S_n)`, `f(C) = 2f(S_{p-1})+2(f(S_{3p-3})-f(S_{2p-2}))=6p^2-10p+4`, `f(B) = 6p^2 - 4p`, `(f(B)-f(C))/2 = 3 p - 2`. Аналогично рассмотренному случаю `n = 3k`, поменяем местами подмножества `X` и `Y` множеств `B` и `C` соответственно; при четном `p` `X = {4p - 1,\ 4p + 1}`, `Y = {p,\ 4p + 2}`, при нечетном `X = {5p - 4}`, `Y = {2p-2}`.