Задачи из Математического Просвещения №10 (2006)

[maxal]

maxal писал(а):

3. (Э.Б.Винберг) Рассмотрим циклические слова с отмеченным началом из 0 и 1 с четным числом нулей. Припишем единицам слова знаки $+$ и $-$ так, чтобы знаки соседних единиц совпадали или отличались в зависимости от четности числа нулей между ними (например, идущие подряд единицы берутся с одинаковым знаком). Сигнатурой слова назовем абсолютную величину алгебраической суммы единиц. Докажите, что число слов длины $n$ и сигнатуры $n-2k$ равно числу сочетаний из $n$ по $k$ при $n-2k>0$ и вдвое меньше при $n-2k=0$.

Ответ должен быть в два раза больший: "число слов длины $n$ и сигнатуры $n-2k$ равно числу сочетаний из $n$ по $k$ при $n-2k=0$ и вдвое больше при $n-2k>0$".
Например, для $n=6$ и $k=2$ имеем такие циклические слова сигнатуры $n-2k=2$ (в скобках указано число способов отметить начало):
110000 (6)
100100 (3)
1110-10 (6)
-1-10000 (6)
-100-100 (3)
-1-1-1010 (6)
Общее число слов равно $30=2{6\choose 2}.$

Будем считать, что количество +1 неменьше количества -1, и доказывать, что количество искомых слов равно ${n\choose k}$. Слова, в которых больше -1ц чем +1ц, получаются сменой знака у всех единиц одновременно и, таким образом, количество слов удваивается.

Заметим, что если сигнатура слова длины $n$ равна $n-2k,$ то количество нулей плюс удвоенное количество -1ц равно $2k.$ Добавим к каждой -1це по нулю с обоих сторон, тогда количество нулей станет равным $2k,$ и между каждыми двумя единицами (независимо от знака) будет стоять четное число единиц, причем каждая -1ца является изолированной нулями, в то время как +1цы могут стоять рядом.
Заменим последовательные два нуля на 2-ку, так что у нас будет $k$ 2-ек.

Таким образом, задача сводится к следующей: есть $k$ двоек, расставленных по окружности, между которыми можно вставлять плюс или минус единицы, причем каждая -1 является изолированной, а +1 может идти сразу несколько за раз. В последсвие каждая каждая 2-ка заменяется на два нуля, и вокруг каждой -1 удаляются нули справа и слева.
Итак, из $k$ промежутков между двойками мы выбираем $s$ для -1ц (число способов ${k\choose s}$), а под остальным $k-s$ промежуткам раскидываем $n-2k+s$ 1ц (число способов ${(n-2k+s)+(k-s)-1\choose (k-s)-1}={n-k-1\choose k-s-1}$). Таким образом, число таких слов равно:

$$\sum_{s=0}^{k} {k\choose s} {n-k-1\choose k-s-1} = {n-1\choose k-1}.$$

Но здесь мы не учитывали отмеченное начало. Отметить начало в построенной циклической последовательности можно $n$ способами, но последовательности совпадающие при повороте будут давать одинаковые слова. Нетрудно понять, что каждое конкретное слово с отмеченным началом будет посчитано ровно $k$ раз (количество поворотов, при которых положение 2-ек совпадает). Поэтому ответом будет $\frac{n}{k}{n-1\choose k-1} = {n\choose k}.$

[Dandan]

я так понимаю слова +10-10 и -10+10 считаются одинаковыми (т.е. на знак мы не смотрим, мы ж говорим только о словах из 0 и 1).

[maxal]

Dandan писал(а):

я так понимаю слова +10-10 и -10+10 считаются одинаковыми (т.е. на знак мы не смотрим, мы ж говорим только о словах из 0 и 1).

Если так, то все ok. Но на решение это не влияет.