среднее количество двоичных векторов, удовл. равенству

[a1020]

помогите найти среднее количество векторов, удовлетворяющих равенству
${X_1}{X_2} \oplus {X_2}{X_3} \oplus ..... \oplus {X_{n - 1}}{X_n} = \varphi ({X_1}, \ldots ,{X_n})$

нужно рассмотривать все булевые функции зависящие от$({X_1}, \ldots ,{X_n})$

[/math]

[Xaositect]

Не понял формулировку.
Требуется найти среднее по всем булевым функциям $\varphi$ от $n$ переменных количество наборов, удовлетворяющих равенству?

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

Если так, то все просто
$\frac{1}{|P_2(n)|} \sum\limits_{\varphi\in P_2(n)}\#\{x|f(x) = \varphi(x)\}$ не зависит от $f$.

Так что, скорее всего, имелось в виду что-то другое

[a1020]

Xaositect писал(а):

Не понял формулировку.
Требуется найти среднее по всем булевым функциям $\varphi$ от $n$ переменных , удовлетворяющих равенству?

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

Если так, то все просто
$\frac{1}{|P_2(n)|} \sum\limits_{\varphi\in P_2(n)}\#\{x|f(x) = \varphi(x)\}$ не зависит от $f$.

Так что, скорее всего, имелось в виду что-то другое

количество наборов

\[({X_1}, \ldots ,{X_n})\]

которые удовлетворяют равенству

\[{X_1}{X_2} \oplus {X_2}{X_3} \oplus ... \oplus {X_{n - 1}}{X_n} = 1\]

, я подсчитал что ровняеться

\[{2^{n - 1}} - {2^{\left\lfloor {\frac{n} {2}} \right\rfloor - 1 + n(\bmod 2)}}\]

существует

\[{2^{{2^n}}}\]

булевых функций зависящих от

\[({X_1}, \ldots ,{X_n})\]

. Нужно для каждой функции подсчитать количество наборов, которые удовлетворяют ${X_1}{X_2} \oplus {X_2}{X_3} \oplus ..... \oplus {X_{n - 1}}{X_n} = \varphi ({y_1}, \ldots ,{y_k})$, сложить их и делить на

\[{2^{{2^n}}}\]

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

a1020 писал(а):

Xaositect писал(а):

Не понял формулировку.
Требуется найти среднее по всем булевым функциям $\varphi$ от $n$ переменных , удовлетворяющих равенству?

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

Если так, то все просто
$\frac{1}{|P_2(n)|} \sum\limits_{\varphi\in P_2(n)}\#\{x|f(x) = \varphi(x)\}$ не зависит от $f$.

Так что, скорее всего, имелось в виду что-то другое

количество наборов

\[({X_1}, \ldots ,{X_n})\]

которые удовлетворяют равенству

\[{X_1}{X_2} \oplus {X_2}{X_3} \oplus ... \oplus {X_{n - 1}}{X_n} = 1\]

, я подсчитал что ровняеться

\[{2^{n - 1}} - {2^{\left\lfloor {\frac{n} {2}} \right\rfloor - 1 + n(\bmod 2)}}\]

существует

\[{2^{{2^n}}}\]

булевых функций зависящих от

\[({X_1}, \ldots ,{X_n})\]

. Нужно для каждой функции подсчитать количество наборов, которые удовлетворяют ${X_1}{X_2} \oplus {X_2}{X_3} \oplus ..... \oplus {X_{n - 1}}{X_n} = \varphi ({y_1}, \ldots ,{y_k})$, сложить их и делить на

\[{2^{{2^n}}}\]

простите, вышла апечатка, нужно для каждой функции подсчитать количество наборов, которые удовлетворяют ${X_1}{X_2} \oplus {X_2}{X_3} \oplus ..... \oplus {X_{n - 1}}{X_n} = \varphi ({X_1}, \ldots ,{X_n})$, сложить их и делить на

\[{2^{{2^n}}}\]

[/quote]

[Xaositect]

Проведите замену $\varphi(x_1,\dots, x_n) = x_1x_2\oplus x_2x_3\oplus\dots\oplus x_{n-1}x_n \oplus \psi(x_1,\dots,x_n)$
Если $\varphi$ пробегает все функции, то и $\psi$ пробегает все функции.

[a1020]

Xaositect писал(а):

Проведите замену $\varphi(x_1,\dots, x_n) = x_1x_2\oplus x_2x_3\oplus\dots\oplus x_{n-1}x_n \oplus \psi(x_1,\dots,x_n)$
Если $\varphi$ пробегает все функции, то и $\psi$ пробегает все функции.

не понял мысли, чем это поможет в подсчете?

[Xaositect]

Количество наборов, где $\varphi(x_1,\dots, x_n) = x_1x_2\oplus x_2x_3\oplus\dots\oplus x_{n-1}x_n$, равно количеству наборов, где $\psi(x_1,\dots,x_n) = 0$

[a1020]

Xaositect писал(а):

Количество наборов, где $\varphi(x_1,\dots, x_n) = x_1x_2\oplus x_2x_3\oplus\dots\oplus x_{n-1}x_n$, равно количеству наборов, где $\psi(x_1,\dots,x_n) = 0$

Спасибо, понял, только как доказать что

\[\psi ({X_1}, \ldots ,{X_n})\]

пробегает все функции?

[Xaositect]

a1020 в сообщении #207810 писал(а):

Спасибо, понял, только как доказать что \[\psi ({X_1}, \ldots ,{X_n})\] пробегает все функции?

Ну это совсем просто.
Для любого $\psi$ существует $\varphi$, из которого оно получается. Формулу напишите сами

[a1020]

Xaositect писал(а):

a1020 в сообщении #207810 писал(а):

Спасибо, понял, только как доказать что \[\psi ({X_1}, \ldots ,{X_n})\] пробегает все функции?

Ну это совсем просто.
Для любого $\psi$ существует $\varphi$, из которого оно получается. Формулу напишите сами

спасибо большое