Задача 6. В марсианском алфавите k букв, и два слова называются похожими, если в них одинаковое количество букв и они отличаются лишь в одном месте (например, СОЧИ и НОЧИ). Докажите, что все слова в языке можно разбить на k групп, в каждой из которых все слова не похожи друг на друга.

Для решения этой задачи воспользуемся методом раскраски или разбиения по остаткам. Пусть длина слов в языке равна $n$. Любое слово в языке можно представить как последовательность букв $(x_1, x_2, \dots, x_n)$, где каждая буква $x_i$ принадлежит множеству из $k$ букв, которые мы можем пронумеровать числами от $0$ до $k-1$. Определим для каждого слова его "сумму" $S$ по модулю $k$: $S = (x_1 + x_2 + \dots + x_n) \pmod k$ Теперь разобьем все слова на $k$ групп по значению их суммы $S$ (от $0$ до $k-1$). Докажем, что в каждой группе слова не похожи друг на друга: 1. Два слова называются похожими, если они отличаются ровно в одном месте. 2. Пусть слово $A = (a_1, a_2, \dots, a_n)$ и слово $B = (b_1, b_2, \dots, b_n)$ похожи. Это значит, что они отличаются только в одной позиции $j$, то есть $a_i = b_i$ при всех $i \neq j$, а $a_j \neq b_j$. 3. Разность их сумм будет равна: $S_A - S_B = (a_1 + \dots + a_j + \dots + a_n) - (b_1 + \dots + b_j + \dots + b_n) = a_j - b_j \pmod k$ 4. Поскольку $a_j \neq b_j$ и оба значения лежат в диапазоне от $0$ до $k-1$, их разность $a_j - b_j$ не может быть кратна $k$. Значит, $a_j - b_j \not\equiv 0 \pmod k$. 5. Следовательно, $S_A \neq S_B$, то есть слова $A$ и $B$ имеют разные суммы и обязаны попасть в разные группы. Таким образом, в любой группе с одинаковой суммой $S$ не может быть двух похожих слов. Что и требовалось доказать.