На каком числе наборов логич. ф-ция принимает значение 1

[Городецкий Павел]

На каком числе наборов ф-ция принимает значение 1

$$f(x_1 ,...,x_n ) = x_1 x_2 \oplus x_2 x_3 \oplus ... \oplus x_{n - 1} x_n $$

Понятно что, если нечетное число произведений равны 1 , то и функция равна 1. Произведения равны 1 когда оба сомножителя 1, но при этом они влияют на соседние и т.д. Наверное такое рассуждение не совсем красивое, поэтому трудно как-то подсчитать, подскажите пожалуйста покрасивее.

[PAV]

Используйте соображение, что в ряду $x_1,\ldots,x_n$ каждая пара соседних единиц дает ровно одну единицу в рассматриваемую сумму.

Ответ можно выразить через общее количество единиц в наборе переменных и количество блоков последовательных единиц.

[Городецкий Павел]

Никак не могу учесть правильно наборы вида ...111..., которые дают $1 \oplus 1 = 0$

[PAV]

Сколько единиц в сумму даст блок длины $k$? Блоком называем последовательность переменных, индексы которых идут подряд, которые все равны 1 и к который нельзя расширить ни влево, ни вправо.

[Городецкий Павел]

блок длины $k$ даст в сумму $k - 1$ единиц, а дальше только остается поиграть четностью? так да?

[PAV]

Городецкий Павел писал(а):

блок длины $k$ даст в сумму $k - 1$ единиц

Верно. В частности, блок длины 1 не даст ни одной единицы в сумму.

А теперь пусть нам известно, что в ряду переменных имеется $m$ блоков единиц и их совокупная длина равна $k$. Как выразить число единиц в искомой сумме через эти параметры?

[Городецкий Павел]

Вот тут уже хуже - мне кажется что эта задача равносильна размещению $k$ непомеченных частиц по $ m $ помеченным ящикам (разбиралось на семинаре) т.е.

$$C_{k + m - 1}^k $$

[PAV]

Нет, все проще гораздо. Смотрите: для каждого блока мы берем число единиц в нем и вычитаем 1.

Добавлено спустя 1 минуту 4 секунды:

Например, пусть есть два блока ($m=2$) и их длины равны $k_1$ и $k_2$. Сколько тогда единиц будет в сумме?

[Городецкий Павел]

Если известна длина каждого блока, то число единиц

$$\sum\limits_{i = 1}^m {(k_i - 1)$$

где

$${\sum\limits_{i = 1}^m {k_i = k} }$$

[PAV]

Правильно. И раскрывая скобки получаем, что количество единиц в сумме равно просто $k-m$. Функция равна 1 тогда и только тогда, когда это число нечетное.

Может быть, существуют и другие способы охарактеризовать все наборы переменных, на которых данная функция равна 1. Но, по-моему, этот наиболее простой.

Добавлено спустя 8 минут 21 секунду:

Не очень внимательно посмотрел, что речь идет о подсчете всех наборов. Это надо подумать...

[Городецкий Павел]

Супер
То есть в итоге необходимо найти количество наборов у которых $k-m$ нечетно, где m - количество блоков, а k - совокупная длина.
Только я что-то опять подтормаживаю как это сделать

[PAV]

Придумалось следующее соображение, основанное на рекуррентных соотношениях.

Обозначим через $f_1(n,0)$ число всех наборов переменных длины $n$, таких что $x_n=0$ и искомая функция равна 1. Аналогично $f_1(n,1)$ - все такие наборы, оканчивающиеся на 1. Сумма $f_1(n)=f_1(n,0)+f_1(n,1)$ - то, что требуется найти.

Используем тот факт (вытекающий из полученного результата), что если набор оканчивается на 0, то при приписывании к нему еще одной переменной значение рассматриваемой функции не меняется. А если набор оканчивается на 1, то от приписывания нуля значение функции не меняется, а от приписывания единицы - меняется на противоположное.

Тогда можно записать следующие рекуррентные соотношения:

$$f_1(n,0)=f_1(n-1,0)+f_1(n-1,1)=f_1(n-1)$$

$$f_1(n,1)=f_1(n-1,0)+f_0(n-1,1)$$

Складываем и учитываем, что сумма $f_1(n-1,1)+f_0(n-1,1)$ равна числу всех наборов длины $n-1$, оканчивающихся на 1, т.е. $2^{n-2}$.

$$f_1(n)=f_1(n,0)+f_1(n,1)=2f_1(n-1,0)+2^{n-2}=2f_1(n-2)+2^{n-2}$$

Получилось рекурретное соотношение. Правда, не соображу, как его решать...

Добавлено спустя 3 минуты 4 секунды:

Впрочем, нет, все ясно: если теперь подставить вместо $f_1(n-2)$ такое же рекуррентное соотношение и так далее, то видно, что получается сумма геометрической прогрессии. В общем, далее уже можно считать. Нужно только отдельно рассмотреть случаи четных и нечетных $n$.

[Городецкий Павел]

PAV
Я понял - я просто теперь думаю как это решение представить без рекурентности - все-таки 1 курс вечернего - мы еще пока не проходили
Я думаю тогда так написать (извините за плагиат):

Обозначим через $N1_{1,n}$ число всех наборов переменных длины $n$, таких что $x_n=0$ и искомая функция равна 1. Аналогично $N2_{0,n}$ - все такие наборы, оканчивающиеся на 1. Сумма $N_n=N1_{1,n}+N2_{0,n}$ - то, что требуется найти.

Используем тот факт (вытекающий из полученного результата), что если набор оканчивается на 0, то при приписывании к нему еще одной переменной значение рассматриваемой функции не меняется. А если набор оканчивается на 1, то от приписывания нуля значение функции не меняется, а от приписывания единицы - меняется на противоположное.

и так далее по тексту

[PAV]

Да в общем-то это одно и то же, Вы просто слово "рекуррентность" можете не произносить... Пишите как хотите, главное, чтобы было правильно.

А вообще по-моему не надо бояться показать какие-то знания, которым Вас не учили.

[RIP]

Не до конца вникал в рассуждения, но если надо решить рекуррентность

$$f_1(n)=2f_1(n-2)+2^{n-2},$$

то можно просто поделить это соотношение на $2^{\frac n2}$. Если обозначить $g(n)=f_1(n)2^{-\frac n2}$, то получим

$$g(n)=g(n-2)+2^{\frac n2-2}.$$

Или переписать в виде

$$f_1(n)-2^{n-1}=2(f_1(n-2)-2^{n-3}).$$