2014-06-08
Про числа $n > 3, k = \left [ \frac{1}{6} n(n+1) \right ]$ и множество $X_{n}$, состоящее из $n(n + 1)/2$ элементов, известно, что $k$ элементов этого множества имеют синий цвет, $k$ элементов - красный цвет, а все остальные элементы - белый цвет. Доказать, что множество $X_{n}$ можно разбить на $n$ попарно непересекающихся подмножеств $A_{1}, \cdots, A_{n}$ так, чтобы для любого значения $m = 1, \cdots, n$ подмножество $A_{m}$ имело ровно $m$ элементов и причем одного цвета.
Решение:
n | $\frac{n(n+1)}{2}$ | k | Синий | Красный | Белый |
4 | 10 | 3 | 1;2 | 3 | 4 |
5 | 15 | 5 | 1;4 | 2;3 | 5 |
6 | 21 | 7 | 1;6 | 2;5 | 3;4 |
7 | 28 | 9 | 4;5 | 3;6 | 1;2;7 |
8 | 36 | 12 | 5;7 | 4;8 | 1;2;3;6 |
9 | 45 | 15 | 6;9 | 7;8 | 1;2;3;4;5 |
Докажем утверждение индукцией по $n > 3$. При $n =4, 5, 6, 7, 8, 9$ возможные разбиения множества $X_{n}$ на подмножества $A_{1}, \cdots, A_{2}$ указаны в таблице, где для каждого значения $n$ и каждого из трех цветов указаны номера $m$ тех множеств $A_{m}$, которые должны состоять из элементов соответствующего цвета (например, при $n=6$ элементы множеств $A_{2}$ и $A_{5}$ должны быть красными). Пусть теперь $n \geq 10$ и для чисел, меньших $n$, в частности для числа $n – 6$, утверждение доказано. Разбиение множества $X_{n}$ построим следующим образом: множества $A_{1}, \cdots, A_{n-6}$ составим из элементов тех же цветов, что и в разбиении множества $X_{n-6}$. Множества $A_{n-5}, A_{n}$ составим из элементов синего цвета, множества $A_{n-3}, A_{n-2}$ - из элементов красного цвета, а множества $A_{n-4}, A_{n-1}$ - из элементов белого цвета. Полученное разбиение удовлетворяет условию задачи, так как количество синих, красных и белых элементов (в отдельности) множества $X_{n}$ больше количества соответствующих элементов множества $X_{n-0}$ на одну и ту же величину, равную $2n – 5$.